{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "AUC_tutorial.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dOWsiMm5YDb7",
        "colab_type": "text"
      },
      "source": [
        "## AUC in CatBoost"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Rezl56dveu0A",
        "colab_type": "text"
      },
      "source": [
        "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/catboost/catboost/tree/master/catboost/tutorial/metrics/AUC_tutorial.ipynb)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-YOfI2AtQKQy",
        "colab_type": "text"
      },
      "source": [
        "The tutorial is dedicated to The Area Under the Receiver Operating Characteristic (ROC) Curve (AUC) and it's implementations in CatBoost for binary classification, multiclass classification and ranking problems.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xLYUxiIw2-Ka",
        "colab_type": "text"
      },
      "source": [
        "### Library installation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5xv97zZ-ZzfX",
        "colab_type": "code",
        "outputId": "087bb2ba-bd80-4c10-ec7d-b0a682cf07b7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        }
      },
      "source": [
        "!pip install --upgrade catboost\n",
        "!pip install --upgrade ipywidgets\n",
        "!pip install shap\n",
        "!pip install --upgrade sklearn\n",
        "# !pip install --upgrade numpy\n",
        "!jupyter nbextension enable --py widgetsnbextension"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting catboost\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/94/ec/12b9a42b2ea7dfe5b602f235692ab2b61ee1334ff34334a15902272869e8/catboost-0.22-cp36-none-manylinux1_x86_64.whl (64.4MB)\n",
            "\u001b[K     |████████████████████████████████| 64.4MB 61kB/s \n",
            "\u001b[?25hRequirement already satisfied, skipping upgrade: matplotlib in /usr/local/lib/python3.6/dist-packages (from catboost) (3.2.1)\n",
            "Requirement already satisfied, skipping upgrade: pandas>=0.24.0 in /usr/local/lib/python3.6/dist-packages (from catboost) (1.0.3)\n",
            "Requirement already satisfied, skipping upgrade: scipy in /usr/local/lib/python3.6/dist-packages (from catboost) (1.4.1)\n",
            "Requirement already satisfied, skipping upgrade: graphviz in /usr/local/lib/python3.6/dist-packages (from catboost) (0.10.1)\n",
            "Requirement already satisfied, skipping upgrade: numpy>=1.16.0 in /usr/local/lib/python3.6/dist-packages (from catboost) (1.18.2)\n",
            "Requirement already satisfied, skipping upgrade: plotly in /usr/local/lib/python3.6/dist-packages (from catboost) (4.4.1)\n",
            "Requirement already satisfied, skipping upgrade: six in /usr/local/lib/python3.6/dist-packages (from catboost) (1.12.0)\n",
            "Requirement already satisfied, skipping upgrade: cycler>=0.10 in /usr/local/lib/python3.6/dist-packages (from matplotlib->catboost) (0.10.0)\n",
            "Requirement already satisfied, skipping upgrade: python-dateutil>=2.1 in /usr/local/lib/python3.6/dist-packages (from matplotlib->catboost) (2.8.1)\n",
            "Requirement already satisfied, skipping upgrade: pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 in /usr/local/lib/python3.6/dist-packages (from matplotlib->catboost) (2.4.6)\n",
            "Requirement already satisfied, skipping upgrade: kiwisolver>=1.0.1 in /usr/local/lib/python3.6/dist-packages (from matplotlib->catboost) (1.1.0)\n",
            "Requirement already satisfied, skipping upgrade: pytz>=2017.2 in /usr/local/lib/python3.6/dist-packages (from pandas>=0.24.0->catboost) (2018.9)\n",
            "Requirement already satisfied, skipping upgrade: retrying>=1.3.3 in /usr/local/lib/python3.6/dist-packages (from plotly->catboost) (1.3.3)\n",
            "Requirement already satisfied, skipping upgrade: setuptools in /usr/local/lib/python3.6/dist-packages (from kiwisolver>=1.0.1->matplotlib->catboost) (46.0.0)\n",
            "Installing collected packages: catboost\n",
            "Successfully installed catboost-0.22\n",
            "Requirement already up-to-date: ipywidgets in /usr/local/lib/python3.6/dist-packages (7.5.1)\n",
            "Requirement already satisfied, skipping upgrade: nbformat>=4.2.0 in /usr/local/lib/python3.6/dist-packages (from ipywidgets) (5.0.5)\n",
            "Requirement already satisfied, skipping upgrade: traitlets>=4.3.1 in /usr/local/lib/python3.6/dist-packages (from ipywidgets) (4.3.3)\n",
            "Requirement already satisfied, skipping upgrade: ipython>=4.0.0; python_version >= \"3.3\" in /usr/local/lib/python3.6/dist-packages (from ipywidgets) (5.5.0)\n",
            "Requirement already satisfied, skipping upgrade: ipykernel>=4.5.1 in /usr/local/lib/python3.6/dist-packages (from ipywidgets) (4.6.1)\n",
            "Requirement already satisfied, skipping upgrade: widgetsnbextension~=3.5.0 in /usr/local/lib/python3.6/dist-packages (from ipywidgets) (3.5.1)\n",
            "Requirement already satisfied, skipping upgrade: jupyter-core in /usr/local/lib/python3.6/dist-packages (from nbformat>=4.2.0->ipywidgets) (4.6.3)\n",
            "Requirement already satisfied, skipping upgrade: jsonschema!=2.5.0,>=2.4 in /usr/local/lib/python3.6/dist-packages (from nbformat>=4.2.0->ipywidgets) (2.6.0)\n",
            "Requirement already satisfied, skipping upgrade: ipython-genutils in /usr/local/lib/python3.6/dist-packages (from nbformat>=4.2.0->ipywidgets) (0.2.0)\n",
            "Requirement already satisfied, skipping upgrade: decorator in /usr/local/lib/python3.6/dist-packages (from traitlets>=4.3.1->ipywidgets) (4.4.2)\n",
            "Requirement already satisfied, skipping upgrade: six in /usr/local/lib/python3.6/dist-packages (from traitlets>=4.3.1->ipywidgets) (1.12.0)\n",
            "Requirement already satisfied, skipping upgrade: setuptools>=18.5 in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (46.0.0)\n",
            "Requirement already satisfied, skipping upgrade: pickleshare in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (0.7.5)\n",
            "Requirement already satisfied, skipping upgrade: simplegeneric>0.8 in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (0.8.1)\n",
            "Requirement already satisfied, skipping upgrade: pygments in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (2.1.3)\n",
            "Requirement already satisfied, skipping upgrade: pexpect; sys_platform != \"win32\" in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (4.8.0)\n",
            "Requirement already satisfied, skipping upgrade: prompt-toolkit<2.0.0,>=1.0.4 in /usr/local/lib/python3.6/dist-packages (from ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (1.0.18)\n",
            "Requirement already satisfied, skipping upgrade: tornado>=4.0 in /usr/local/lib/python3.6/dist-packages (from ipykernel>=4.5.1->ipywidgets) (4.5.3)\n",
            "Requirement already satisfied, skipping upgrade: jupyter-client in /usr/local/lib/python3.6/dist-packages (from ipykernel>=4.5.1->ipywidgets) (5.3.4)\n",
            "Requirement already satisfied, skipping upgrade: notebook>=4.4.1 in /usr/local/lib/python3.6/dist-packages (from widgetsnbextension~=3.5.0->ipywidgets) (5.2.2)\n",
            "Requirement already satisfied, skipping upgrade: ptyprocess>=0.5 in /usr/local/lib/python3.6/dist-packages (from pexpect; sys_platform != \"win32\"->ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (0.6.0)\n",
            "Requirement already satisfied, skipping upgrade: wcwidth in /usr/local/lib/python3.6/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython>=4.0.0; python_version >= \"3.3\"->ipywidgets) (0.1.9)\n",
            "Requirement already satisfied, skipping upgrade: pyzmq>=13 in /usr/local/lib/python3.6/dist-packages (from jupyter-client->ipykernel>=4.5.1->ipywidgets) (17.0.0)\n",
            "Requirement already satisfied, skipping upgrade: python-dateutil>=2.1 in /usr/local/lib/python3.6/dist-packages (from jupyter-client->ipykernel>=4.5.1->ipywidgets) (2.8.1)\n",
            "Requirement already satisfied, skipping upgrade: jinja2 in /usr/local/lib/python3.6/dist-packages (from notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (2.11.1)\n",
            "Requirement already satisfied, skipping upgrade: nbconvert in /usr/local/lib/python3.6/dist-packages (from notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (5.6.1)\n",
            "Requirement already satisfied, skipping upgrade: terminado>=0.3.3; sys_platform != \"win32\" in /usr/local/lib/python3.6/dist-packages (from notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.8.3)\n",
            "Requirement already satisfied, skipping upgrade: MarkupSafe>=0.23 in /usr/local/lib/python3.6/dist-packages (from jinja2->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (1.1.1)\n",
            "Requirement already satisfied, skipping upgrade: testpath in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.4.4)\n",
            "Requirement already satisfied, skipping upgrade: mistune<2,>=0.8.1 in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.8.4)\n",
            "Requirement already satisfied, skipping upgrade: bleach in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (3.1.4)\n",
            "Requirement already satisfied, skipping upgrade: entrypoints>=0.2.2 in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.3)\n",
            "Requirement already satisfied, skipping upgrade: defusedxml in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.6.0)\n",
            "Requirement already satisfied, skipping upgrade: pandocfilters>=1.4.1 in /usr/local/lib/python3.6/dist-packages (from nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (1.4.2)\n",
            "Requirement already satisfied, skipping upgrade: webencodings in /usr/local/lib/python3.6/dist-packages (from bleach->nbconvert->notebook>=4.4.1->widgetsnbextension~=3.5.0->ipywidgets) (0.5.1)\n",
            "Collecting shap\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/a8/77/b504e43e21a2ba543a1ac4696718beb500cfa708af2fb57cb54ce299045c/shap-0.35.0.tar.gz (273kB)\n",
            "\u001b[K     |████████████████████████████████| 276kB 4.7MB/s \n",
            "\u001b[?25hRequirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from shap) (1.18.2)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.6/dist-packages (from shap) (1.4.1)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.6/dist-packages (from shap) (0.22.2.post1)\n",
            "Requirement already satisfied: pandas in /usr/local/lib/python3.6/dist-packages (from shap) (1.0.3)\n",
            "Requirement already satisfied: tqdm>4.25.0 in /usr/local/lib/python3.6/dist-packages (from shap) (4.38.0)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.6/dist-packages (from scikit-learn->shap) (0.14.1)\n",
            "Requirement already satisfied: python-dateutil>=2.6.1 in /usr/local/lib/python3.6/dist-packages (from pandas->shap) (2.8.1)\n",
            "Requirement already satisfied: pytz>=2017.2 in /usr/local/lib/python3.6/dist-packages (from pandas->shap) (2018.9)\n",
            "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.6/dist-packages (from python-dateutil>=2.6.1->pandas->shap) (1.12.0)\n",
            "Building wheels for collected packages: shap\n",
            "  Building wheel for shap (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for shap: filename=shap-0.35.0-cp36-cp36m-linux_x86_64.whl size=394119 sha256=0cd54ff093f3fa7c422ebaf179c32d05af3053176ca4d30684814e6c332f8d6f\n",
            "  Stored in directory: /root/.cache/pip/wheels/e7/f7/0f/b57055080cf8894906b3bd3616d2fc2bfd0b12d5161bcb24ac\n",
            "Successfully built shap\n",
            "Installing collected packages: shap\n",
            "Successfully installed shap-0.35.0\n",
            "Requirement already up-to-date: sklearn in /usr/local/lib/python3.6/dist-packages (0.0)\n",
            "Requirement already satisfied, skipping upgrade: scikit-learn in /usr/local/lib/python3.6/dist-packages (from sklearn) (0.22.2.post1)\n",
            "Requirement already satisfied, skipping upgrade: joblib>=0.11 in /usr/local/lib/python3.6/dist-packages (from scikit-learn->sklearn) (0.14.1)\n",
            "Requirement already satisfied, skipping upgrade: scipy>=0.17.0 in /usr/local/lib/python3.6/dist-packages (from scikit-learn->sklearn) (1.4.1)\n",
            "Requirement already satisfied, skipping upgrade: numpy>=1.11.0 in /usr/local/lib/python3.6/dist-packages (from scikit-learn->sklearn) (1.18.2)\n",
            "Enabling notebook extension jupyter-js-widgets/extension...\n",
            "      - Validating: \u001b[32mOK\u001b[0m\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "owmddxjvZznU",
        "colab_type": "code",
        "outputId": "8042c57e-c6ee-4bff-f40e-0db7ad5f050f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "import catboost\n",
        "print(catboost.__version__)\n",
        "!python --version"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0.22\n",
            "Python 3.6.9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KjtUdeB_mQ2x",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import pandas as pd\n",
        "import os\n",
        "import numpy as np\n",
        "np.set_printoptions(precision=4)\n",
        "import catboost\n",
        "import sklearn\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "from catboost import datasets, Pool\n",
        "from catboost.utils import get_roc_curve, eval_metric\n",
        "from sklearn import metrics\n",
        "from sklearn.model_selection import train_test_split"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "61BiLiK_3JRg",
        "colab_type": "text"
      },
      "source": [
        "### About AUC\n",
        "\n",
        "The **ROC curve** shows the *model's ability to distinguishing between classes*. \n",
        "\n",
        "The model which randomly assigns a class to object is a 'bad' classifier and has a diagonal ROC curve. The better is the classifier, the higher is the ROC curve. The ROC curve is plotted with TPR, [True Positive Rate](https://en.wikipedia.org/wiki/Receiver_operating_characteristic#Basic_concept), on the y-axis against the FPR, [False Positive Rate](https://en.wikipedia.org/wiki/Receiver_operating_characteristic#Basic_concept), on the x-axis. The curve also could be interpreted in terms of [Sensitivity and Specificity](https://en.wikipedia.org/wiki/Sensitivity_and_specificity) of the model with Sensitivity on the y-axis and (1-Specificity) on the x-axis.\n",
        "\n",
        "Building and visualizing the ROC curve could be used *to measure classification algorithm performance with different probability boundaries* and *select the probability boundary* required to achieve the specified false-positive or false-negative rate.\n",
        "\n",
        "**AUC** is the Area Under the ROC Curve. The best AUC = 1 for a model that ranks all the objects right (all objects with class 1 are assigned higher probabilities then objects of class 0). AUC for the 'bad' classifier is equal to 0.5.\n",
        "\n",
        "AUC is used for binary classification, multiclass classification, and ranking problems. *AUC measures the proportion of correctly ordered objects and the capability of the model to distinguish between the classes*.\n",
        "\n",
        "The AUC has an important statistical property: the *AUC of a classifier is equivalent to the probability that the classifier will rank a randomly chosen positive instance higher than a randomly chosen negative instance*.\n",
        "\n",
        "\n",
        "### CatBoost implementation \n",
        "\n",
        "CatBoost implements AUC for [binary classification](https://catboost.ai/docs/concepts/loss-functions-classification.html), [multiclassification](https://catboost.ai/docs/concepts/loss-functions-multiclassification.html) and [ranking](https://catboost.ai/docs/concepts/loss-functions-ranking.html) problems. AUC is used during training to detect overfitting and select the best model. AUC is also used as a metric for predictions evaluation and comparison with [utils.eval_metric](https://https://catboost.ai/docs/concepts/python-reference_utils_eval_metric.html). See examples of models fitting and AUC calculation with CatBoost in the section [How to use AUC in Catboost on real datasets?](#scrollTo=BP1nOBpvFzPV)\n",
        "\n",
        "\n",
        "### Useful links\n",
        "* Read more about ROC on [Wikipedia](https://en.wikipedia.org/wiki/Receiver_operating_characteristic).\n",
        "\n",
        "* To get an understanding of the ROC curve building from scratch see [the article](https://people.inf.elte.hu/kiss/11dwhdm/roc.pdf).\n",
        "\n",
        "* To get an understanding of AUC$\\mu$ for multiclass classification see [the article](http://proceedings.mlr.press/v97/kleiman19a/kleiman19a.pdf)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k9UPSEWu4spg",
        "colab_type": "text"
      },
      "source": [
        "# Binary classification\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4RbdSB4EMBZs",
        "colab_type": "text"
      },
      "source": [
        "## Calculation rules for binary classification "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wC1rAq58lKGm",
        "colab_type": "text"
      },
      "source": [
        "AUC for binary classification is calculated according to the following formula:\n",
        "\n",
        "$$\n",
        "AUC = \\frac{\\sum_{t_i = 0, t_j = 1} I(a_i, a_j) w_i w_j}{\\sum_{t_i = 0, t_j = 1}{w_i w_j}},\n",
        "$$\n",
        "\n",
        "where $a_i, a_j$ - predictions (probabilities) of objects to belong to the class 1 given by the algorithm.\n",
        "\n",
        "The sum is calculated on all pairs of objects $i, j$ such that:\n",
        "$t_i = 0, t_j = 1$ where $t$ is true true class label.\n",
        "\n",
        "$I$ is an indicator function equal to 1 if objects $i, j$ are ordered correctly:\n",
        "\n",
        "$$\n",
        "I(a_i, a_j) =\n",
        "  \\begin{cases}\n",
        "    1    & \\quad \\text{if } a_i < a_j\\\\\n",
        "    0.5  & \\quad \\text{if } a_i = a_j\\\\\n",
        "    0    & \\quad \\text{if } a_i > a_j\\\\\n",
        "  \\end{cases}\n",
        "$$\n",
        "\n",
        "A user could assign weights to each object to specify the importance of each object in metric calculation. \n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FuXWPlXD8Qev",
        "colab_type": "text"
      },
      "source": [
        "## Simple example of AUC calculation for binary classification "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IG8t5GWy4xwB",
        "colab_type": "text"
      },
      "source": [
        "Let's look at a simple example of ROC curve building and AUC calculation:\n",
        "\n",
        "We have a sample of 10 objects, 4 from class 1 and 6 from class 0 ('class' column). All objects are equally important (weights = 1).\n",
        "Assume we predicted probabilities of objects to come from class 1 ('prediction' column).\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iu-f6jIACyV9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "toy_example = pd.DataFrame({'class': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'prediction': [0.9, 0.4, 0.6, 0.2, 0.8, 0.25, 0.15, 0.4, 0.3, 0.1]})"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TXnHw2KB646y",
        "colab_type": "text"
      },
      "source": [
        "To build the ROC curve we need to sort the dataset in descending order of predicted probabilities."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CegWTbQVD0u0",
        "colab_type": "code",
        "outputId": "3fcc7112-7bb6-4ce1-a881-62475e467085",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 343
        }
      },
      "source": [
        "toy_example.sort_values(by='prediction', ascending=False, inplace=True)\n",
        "toy_example"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>class</th>\n",
              "      <th>prediction</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>0.90</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>0</td>\n",
              "      <td>0.80</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>1</td>\n",
              "      <td>0.60</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>0.40</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>0</td>\n",
              "      <td>0.40</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>8</th>\n",
              "      <td>0</td>\n",
              "      <td>0.30</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>0</td>\n",
              "      <td>0.25</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>0.20</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>0</td>\n",
              "      <td>0.15</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>9</th>\n",
              "      <td>0</td>\n",
              "      <td>0.10</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   class  prediction\n",
              "0      1        0.90\n",
              "4      0        0.80\n",
              "2      1        0.60\n",
              "1      1        0.40\n",
              "7      0        0.40\n",
              "8      0        0.30\n",
              "5      0        0.25\n",
              "3      1        0.20\n",
              "6      0        0.15\n",
              "9      0        0.10"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wd6NRb0XHnpG",
        "colab_type": "text"
      },
      "source": [
        "The denominator $\\sum_{t_i = 0, t_j = 1}{w_i w_j}$ is equal to the number of pairs of objects $i, j$ such that true class $t_i = 0, t_j = 1$. As there are 4 objects from class 1 and 6 objects from class 0, the denominator is equal to 24.\n",
        "\n",
        "For each object from class 1 count the number of objects from class 0, which are below (has less probability) in the sorted dataset.\n",
        "\n",
        "We add +1 of objects ordered correctly (e.g. objects with IDs 0 and 4) and +0.5 if probabilities are equal (e.g. objects with IDs 1 and 7).\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i0v7Rp6ib-b5",
        "colab_type": "text"
      },
      "source": [
        "For example, the object with ID = 1 adds +4.5 to AUC numerator as correctly ordered with objects with IDs: 8, 3, 6, 9 and has equal prediction with object 7:\n",
        "\n",
        "![Binary AUC calculation visualization](https://habrastorage.org/webt/9m/hp/y5/9mhpy5d28dzxyvaeh_tby9ls2yo.jpeg)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SUFRrQQmJM-S",
        "colab_type": "code",
        "outputId": "ceb93199-9e89-4280-affd-e4fd3b19a08d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "denominator = sum(toy_example['class'] == 1) * sum(toy_example['class'] == 0)\n",
        "numerator = (6 + 5 + 4.5 + 2)\n",
        "manually_calculated_auc = numerator / denominator\n",
        "print('Example of manually calculated ROC AUC = {0:.4f}'.format(manually_calculated_auc))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Example of manually calculated ROC AUC = 0.7292\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jbVJ9lBO_6C7",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate the same metric with Catboost and ensure everything is right: "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6Y0gpIShE6fB",
        "colab_type": "code",
        "outputId": "7c19aaa6-ece3-4e02-8351-406454b39855",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "catboost_auc = eval_metric(toy_example['class'], toy_example['prediction'], 'AUC')[0]\n",
        "print('Example of ROC AUC calculated with CatBoost = {0:.4f}'.format(catboost_auc))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Example of ROC AUC calculated with CatBoost = 0.7292\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iQ8bzVckL4ej",
        "colab_type": "text"
      },
      "source": [
        "## ROC curve"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4e6oS_H5EFU4",
        "colab_type": "text"
      },
      "source": [
        "To build a ROC curve put the number of objects of class 1 ($n_1$) in the square with side 1 along the $ y $-axis, and the number of objects of class 0 ($n_0$) along the $ x $-axis.\n",
        "\n",
        "Going by the list of target labels sorted by model predictions in descending order will add $\\frac{1}{n_1}$ along the $y$-axis encountering an object of class 1 and $\\frac{1}{n_0}$ along the $x$-axis encountering an object of class 0.\n",
        "\n",
        "Let's get FPR, TPR with sklearn and visualize the curve. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dUEdCfrkH7cH",
        "colab_type": "code",
        "outputId": "c6866e41-66ae-47ed-e174-2b0c29ddc32c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 343
        }
      },
      "source": [
        "toy_example"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>class</th>\n",
              "      <th>prediction</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>0.90</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>0</td>\n",
              "      <td>0.80</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>1</td>\n",
              "      <td>0.60</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>0.40</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>0</td>\n",
              "      <td>0.40</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>8</th>\n",
              "      <td>0</td>\n",
              "      <td>0.30</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>0</td>\n",
              "      <td>0.25</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>0.20</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>0</td>\n",
              "      <td>0.15</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>9</th>\n",
              "      <td>0</td>\n",
              "      <td>0.10</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   class  prediction\n",
              "0      1        0.90\n",
              "4      0        0.80\n",
              "2      1        0.60\n",
              "1      1        0.40\n",
              "7      0        0.40\n",
              "8      0        0.30\n",
              "5      0        0.25\n",
              "3      1        0.20\n",
              "6      0        0.15\n",
              "9      0        0.10"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WDrsmhWBIP80",
        "colab_type": "text"
      },
      "source": [
        "Going from top to bottom by the 'class' column we go up on the plot if the class is 1 or right if the class is 0. When we meet objects with equal prediction add the number of 1 along y and the number of 0 along x and go by the diagonal of the rectangle. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GgQjuWvtGMnp",
        "colab_type": "code",
        "outputId": "bfc0b10b-3db2-4be8-b6b6-d8cdeb28b537",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        }
      },
      "source": [
        "fpr, tpr, _ = sklearn.metrics.roc_curve(toy_example['class'], toy_example['prediction'])\n",
        "\n",
        "plt.figure()\n",
        "lw = 2\n",
        "plt.plot(fpr, tpr, color='darkorange',\n",
        "         lw=lw, label='ROC curve')\n",
        "plt.fill_between(fpr, tpr, y2=0, color='darkorange', alpha=0.3, label='Area Under Curve (area = %0.2f)' % catboost_auc)\n",
        "plt.plot([0, 1], [0, 1], color='navy', lw=lw, linestyle='--')\n",
        "plt.xlim([0.0, 1.0])\n",
        "plt.ylim([0.0, 1.05])\n",
        "plt.xlabel('False Positive Rate')\n",
        "plt.ylabel('True Positive Rate')\n",
        "plt.title('Receiver operating characteristic curve example')\n",
        "plt.legend(loc=\"lower right\")\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEWCAYAAAB42tAoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nOzdd3gUVRfA4d9JLwRS6Elo0hEE6WJB\nEbACChZEEQuKgIrwISggiFhBFEQEC3ZBRFHsFURAqiIiXWkhIRBaSAgpu/f7Y4awhJQFstmU8z5P\nnuyUvXNmdnfO3Dszd8QYg1JKKZUXH28HoJRSqnjTRKGUUipfmiiUUkrlSxOFUkqpfGmiUEoplS9N\nFEoppfKlicKLROQfEeno7Ti8TURmiMiYIl7mOyIyoSiX6Ski0kdEfjjL9+p3sAiJyDgR+cDbcZwp\nP28HUFyIyA6gCuAAUoDvgMHGmBRPLdMY08RTZRdXItIPuNcYc/GJccaYAd6LyLtEZBxQ1xhz+9mW\nYYz5EPjQjWW9A8QZY0a7vLfMfQfVmdMaxamuN8aUA5oDLYDHvBzPGRMRryV/by7bm3Sbn52SHHuZ\nY4zRP+vu9B3AlS7DLwBfuwy3A5YBh4G/gI4u0yKBt4F44BDwucu064C19vuWAc1yLhOoDqQBkS7T\nWgBJgL89fDew0S7/e6Cmy7wGGARsBbbnsX7dgH/sOBYBjXLE8RiwwS7/bSDoDNZhBLAOSMeqpY4E\n/gWO2mXeYM/bCDjOyVrbYXv8O8AE+3VHIA4YBuwDEoC7XJYXBXwJJAOrgAnAknw+14tdPrfdQD+X\nZb4KfG3HuQI4z+V9U+z5k4E1wCUu08YB84AP7On3Am2A3+3lJADTgACX9zQBfgQOAonA48BVQAaQ\naW+Pv+x5KwBv2eXssdfR157WD1gKvAQcsKf1O7ENALGn7bNj+xs4H7jPXk6Gvawvc37vAV87rhOf\n3Rog9gy36yKsGiMu8S5xGT7luwq8BkzKUfYXwFD7dXXgU2C/Pf9D+XzWgcAkYJe9jWcAwfa0b4AX\nXeadA8yyX58H/GJvzySs2ll4ju/4cKzveKr92VQBvrW3009AhD1vLXsd78PaHyQA/8vx3fnAnf1K\ncfrzegDF5S/HDybG/oFNsYej7S/RNVi1sM72cCV7+tfAx0AE4A9cZo9vYf9g29o/wjvt5QTmssxf\ngP4u8UwEZtivuwPbsHa0fsBoYJnLvAZrJxR54oeRY93q21/wznZ8j9rlBbjEsR6ItctYyskdtzvr\nsNZ+74kf5U1YP3Af4BZ72dXsaf3IsWPn9ESRBYy3Y70GOObyQ5xj/4UAjbF2UrkmCqAm1g+5t11W\nFNDcZZkHsHbwflg7hzku773dnt8PK2ntxU6eWD/2TKCHvY7BQEusH70f1s5iIzDEnj8Ma4cxDAiy\nh9u6lPVBjrjnAzOBUKAysBK432X7ZQEP2ssK5tRE0RVrBx+OlTQauWz77O2cx/d+ONb3voH93guA\nqDPcrosoOFFkf1eBS+3PUOzpEVgHTSe+P2uAJ4AAoA7wH9A1j8/7JWCBXXYY1gHFs/a0qljf4yuA\nPnY5Yfa0uli/jUCgErAYeDnHNlqOlRyi7XL+wPptBGH9dsfa89ay13G2/fk1xUpyV+b8vClgv1Kc\n/rweQHH5s78MKfYPwAA/Yx9VYB0xv59j/u+xdprVACf2jizHPK8BT+UYt5mTicT1R3ov8Iv9Wuwf\nz6X28LfAPS5l+GDtPGvawwa4Ip91GwPMzfH+PdhHL3YcA1ymXwP8ewbrcHcB23Yt0N1+3Y+CE0Ua\n4OcyfR/WTtgXawfdwGVanjUKrFrS/DymvQO8mWOdN+WzDoeAC+zX44DFBazzkBPLxtqh/pnHfNk7\nDnu4ClbNLNhlXG9gocv225WjjOxtirUj3GJvL5+8tnOO7/2J7+DmE59TAeuW33ZdRMGJ4gqXYcGq\nAZz4rvfn5O+gbS7r+hjwdi7LFawDEtdaYXtcathAT6zfVRJwcT7r18P187K3UR+X4U+B11yGH8Ru\nReBkomjoMv0F4K2cnzf57FcK+gyK+k/PUZyqhzEmDGtn1RCoaI+vCdwkIodP/GFVvathHUkfNMYc\nyqW8msCwHO+LxTpayulToL2IVMM6ynICv7mUM8WljINYP4xol/fvzme9qgM7TwwYY5z2/Hm9f6dL\njO6swynLFpG+IrLWZf7zObkt3XHAGJPlMnwMKId1tOeXY3n5rXcsVjNKXvbmsgwAROR/IrJRRI7Y\n61CBU9ch5zrXF5GvRGSviCQDz7jMX1AcrmpiHaUnuGy/mVg1i1yX7coY8wtWs9erwD4ReV1Eyru5\nbHfjPJP1yU12/MbaO87BSoYAt3HyxHxNoHqO797jWMk0p0pYtcw1LvN+Z48/4Uusg43NxpglJ0aK\nSBURmSMie+zP7gNO/74murxOy2W43Kmz5/l7cpXffqVY0USRC2PMr1hHX5PsUbuxMn+4y1+oMeY5\ne1qkiITnUtRu4Okc7wsxxszOZZmHgB+wmmpuw2oGMS7l3J+jnGBjzDLXIvJZpXisLyUAIiJYP/Y9\nLvPEuryuYb/H3XXIXraI1ATeAAZjNVuEYzVriRtxFmQ/VrNLTB5x57Qbq/35jIjIJVjNczdj1RTD\ngSOcXAc4fT1eAzYB9Ywx5bF2aCfm343VbJKbnOXsxqpRVHTZ3uXNqVcn5bsNjTFTjTEtsZrm6mM1\nKRX4PtzfXvnNl4q1wz6ham4h5hieDfSyvzttsQ6aTixne47vXpgx5ppcykzC2mE3cZm3grEuTjnh\naawmwWoi0ttl/DN2TE3tz+52Tv2sz0ZevydX+e1XihVNFHl7GegsIhdgHWFcLyJdRcRXRIJEpKOI\nxBhjErCahqaLSISI+IvIpXYZbwADRKStWEJF5FoRCctjmR8BfYFe9usTZgCPiUgTABGpICI3ncG6\nzAWuFZFOIuKP1VaejnUS7YRBIhIjIpHAKKxzLmezDqFYP7r9dqx3YdUoTkgEYkQk4AziB8AY4wA+\nA8aJSIiINMTaXnn5ELhSRG4WET8RiRKR5m4sKgwrIe0H/ETkCaCgo/IwrJPHKXZcD7hM+wpr5zRE\nRAJFJExE2trTEoFaIuJjr2MC1gHDiyJSXkR8ROQ8EbnMjbgRkdb2Z+WPtdM+jlU7PbGsvBIWwJvA\nUyJSz/6sm4lIVC7z5bdd1wI32p9PXeCegmI2xvyJtaN/E/jeGHPYnrQSOCoiI0Qk2P7tnS8irXMp\nw4n1XX1JRCrb2yJaRLrary8F7sL6vtwJvCIiJ2rUYVjNzkfsccNzln8WxtjboIm93I9zmSfP/Uoh\nLL9QaaLIgzFmP/Ae8IQxZjfWCeXHsXYeu7G+TCe23x1YbeebsNrTh9hlrMZqc52G1ca9DavNNi8L\ngHrAXmPMXy6xzAeeB+bYVeP1wNVnsC6bsY6SXsH6QV6PdSlwhstsH2HtoP7DalaYcDbrYIzZALyI\ndQVQItbJvKUus/yCdfXVXhFJcncdXAzGagbaC7yPdTSankcsu7DOPQzDaq5bi3WCtiDfYzVbbMFq\nNjhO/k1cAP/DqgkexdphZe8YjDFHsU5UXm/HvRW43J78if3/gIj8Yb/ui3Xy9sRVaPNwvzmivL38\nQ3bsB7AujADrap3GdjPH57m8dzLWQcUPWEnvLawTzqcoYLu+hHVlVSLwLm7c32H7COsKwOwDJPvA\n4Dqsy9W3czKZVMijjBFY38/l9u/kJ6CB3fT2HtZ9UXuMMb/Z6/a2Xbt+ErgQq9b4NdbByLn61Y7l\nZ6yruk67IdKN/UqxceJKA1WGiXWz4b3GmJ+8HcuZEpHngarGmDu9HYtSIlILK6n55zjPVqIVu8yl\nVH5EpKHdJCIi0garaWO+t+NSqjTTOyNVSROG1dxUHat540WsG7SUUh6iTU9KKaXypU1PSiml8lXi\nmp4qVqxoatWq5e0wlFKqRFmzZk2SMaZSwXOersQlilq1arF69Wpvh6GUUiWKiOwseK7cadOTUkqp\nfGmiUEoplS9NFEoppfKliUIppVS+NFEopZTKlyYKpZRS+fJYohCRWSKyT0TW5zFdRGSqiGwTkXUi\ncqGnYlFKKXX2PHkfxTtYXVO/l8f0q7G61K6H9bCS1+z/SqniJvMY7FkCxuHtSNRZyMhwFjxTPjyW\nKIwxi+0ud/PSHXjPforbchEJF5Fq9oNblFLFyc+D4J93vB2FOgvDv+zMn/HV8JWzb0Hy5p3Z0Zz6\nMJg4e9xpiUJE7gPuA6hRo0aRBKeUcpFiPzU3rAYE5PVwQ1UcnV/Xn6lLaxIeXOBTGvNUIrrwMMa8\nDrwO0KpVK+3uVilvaXArxFzs7ShUPjZsTeOPf45xew/rKbZ9LzZc1juF1t1LZo1iD6c+gDzGHqeU\nUuoMHUtzMuHVBCa+mYivj9CueSh1awUhItSKOeNH1J/Cm5fHLgD62lc/tQOO6PkJpZQ6c9/+eoTz\nr9nAszMSycqCfj2jiIoovHqAx2oUIjIb6AhUFJE4YCzgD2CMmQF8g/WA9m3AMeAuT8WilFKl0Z69\nGQyZEMe87w4D0KxhMDPGx9L+wnKFuhxPXvXUu4DpBhjkqeUrpVRpN2jcbr746QghwT6Mf7gaD/er\njJ+fFPpySsTJbKWUUpasLJOdDJ5/NBp/P+HFx2OoUf3czkPkR7vwUEqpEuDIUQcPPrmba+/dhtUg\nAw3qBPHJtDoeTRKgNQqllCrWjDF88s1hhjwdR8K+THx9Ye2GNFo0CSmyGLRGoZRSxdS/O9O55p5/\nueXh7STsy6R9i1D++KJhkSYJ0BqFUkoVS5PeTGTMS/EcTzeEl/fl+UejuffmKHx8Cv9kdUE0USil\nVDF0LM3J8XTDHT0imfRYNJWj/L0WiyYKpZQqBvYfyGTz9nQubmXdAzHivip0bFuOS9t4v28tPUeh\nlFJe5HQa3vw4iQZdNnDjwP84eDgLgMBAn2KRJEBrFEop5TXrt6QxYMwulq5JBaBzhzCOpTmJDPdy\nYDloolBKqSKWeszB+Gl7mTzL6pupSkU/Xh4dwy3XRiBS9CerC6KJQimlilivwdv5bnEyIjCwT0We\nHlad8PLFd3dcfCNTSqlSasR9VUhMyuS18TVo2zzU2+EUSBOFUkp5UFaW4ZX39rFjTwZTxliP4OnY\nLozVnzf0yj0RZ0MThVJKecjKv1K5f/Qu1m5MA+C+WyrSpH4wQIlJEqCJQimlCt3h5CwenxTPjNlJ\nGAM1owOYNjY2O0mUNJoolFKqEM356iBDJsSRmJSFnx8Mu7sKYwZXJTTE19uhnTVNFEopVYh+WHKU\nxKQsOrQM5bXxNWjaoGTWIlxpolBKqXOQnu5kT2ImdWoEAvDCo9Fc0qocd94YWaLOQ+RHu/BQSqmz\n9MvvR2l23Uau7b+NjAwnABUj/birl3d6efUUTRRKKXWGEpMyuWPYDjrdsZUt29MBiNub6eWoPEeb\nnpRSyk1Op+GNj5MYOTGew8kOggKF0YOqMvzeKgQElN7jbk0USinlphse+I8FPx8BoOsl5Xl1XCzn\n1Qz0clSep4lCKaXcdGPXcFauS2XK6Fhuuia8WHbg5wmaKJRSKg8LfjpM3N5MBt5eCYC+N0RyY5dw\nwsqV3HsizoYmCqWUymFXfAYPjd/NFz8dITBAuOrS8tSpEYiIlLkkAZoolFIqW2amYeq7+xg7NYHU\nY07CQn2YMLQ6NaMDvB2aV2miUEopYPmfqdw/ZhfrNlkd+N10dTgvjYohumrZThKgiUIppQAY83I8\n6zalUTvW6sDvmo4VvB1SsaGJQilVJhljOJripHyYdc5h2thY3pt/gFEDqxESXHrviTgbujWUUmXO\n5v+Oc2Xfbdw46D+MMQA0qBPE08OiNUnkQmsUSqky43i6k2df28tzMxPJyDRERfiyIy6D2rGl/6a5\nc6GJQilVJvy4JJmBY3ezbafVN9PdvaJ4YUQ0URG6GyyIR+tYInKViGwWkW0iMjKX6TVEZKGI/Cki\n60TkGk/Go5Qqe4wx3D1yJ136bWPbznQa1w1i8ez6vPVcTU0SbvLYVhIRX+BVoDMQB6wSkQXGmA0u\ns40G5hpjXhORxsA3QC1PxaSUKntEhFrRAQQHCU8MrsbQuyuX6g78PMGT6bQNsM0Y8x+AiMwBugOu\nicIA5e3XFYB4D8ajlCoj1m44RsL+TK6+zLrEdcR9VbijR6SeizhLnkyr0cBul+E4e5yrccDtIhKH\nVZt4MLeCROQ+EVktIqv379/viViVUqXA0RQHQ5+Oo2WPTdw5fCcHD2cBEBjoo0niHHi7/tUbeMcY\nEwNcA7wvIqfFZIx53RjTyhjTqlKlSkUepFKqeDPGMP+HwzS+agMvvb0PgNu6ReDvVzZ6d/U0TzY9\n7QFiXYZj7HGu7gGuAjDG/C4iQUBFYJ8H41JKlSI796QzeNxuvlqYDECrpiHMfKoGF54f4uXISg9P\n1ihWAfVEpLaIBAC3AgtyzLML6AQgIo2AIEDblpRSbjHG0HPQdr5amEz5cj5MGxvL8nkNNEkUMo/V\nKIwxWSIyGPge8AVmGWP+EZHxwGpjzAJgGPCGiDyCdWK7nzlxm6RSSuXB6TT4+AgiwqSR0cyYncRL\no2KoVtnf26GVSh69iNgY8w3WSWrXcU+4vN4AdPBkDEqp0uPAoSxGTrRasN94piYAHduF0bFdmDfD\nKvW8fTJbKaUKZIzh3c8O0LDLBt6ce4D35h8kLiHD22GVGZoolFLF2sZtaVzeZyv9Ht1J0qEsOrYt\nx19fNSKmmj4noqjo/etKqWLJGMMTLyfw/OuJZGYaKkb48eLj0dzRIxIRvey1KGmiUEUjMw3+fgOO\n6ZXPJdKhrUW+SBFhT2ImmZmG/rdE8dzwaCLDdZflDbrVleelH4HPu0HcYm9Hos6VX7BHi49PzCDp\nUBbNGlqXt77waDT33BRFh5blPLpclT9NFMqzju2DT6+CfX9CYARUvwjE19tRqbMRFA6VmnqkaIfD\n8NqH+xk1OZ7oKgGs/bIhAQE+VIz0o2KkJglv00ShPCd5J8zrAoe2QEgVaP0oRNTzdlSqmPlj/THu\nH7OL1X8fA+DS1gEkpzipGKnX2hQXmiiUZxzYaCWJlDgIi4U2I63/StmSjzoY83I8097fj9MJMVX9\nmfpELD06V9CT1cWM24lCREKMMcc8GYwqJfautpqbjh+A8LrQeiSEVvZ2VKoYMcZw6W1b+GtjGr6+\nMPTuyox7qBph5bRZsjgqsG4nIheJyAZgkz18gYhM93hkqmTatRDmXm4liagm0P4JTRLqNCLCI3dV\nps0FIaye35AXH4/RJFGMuVOjeAnoit2hnzHmLxG51KNRqZJp6+fw9a3gSIcqraDVMPAP9XZUqhjI\nyHAyedY+fH2F4f2rAND3hkhu7x6Jr682MxV3bjU9GWN252gzdHgmHFVirX8HfrgHjBOiL4UWD4Kf\nPihGwW+rUhgwZhcbth0nMEDoe0MkVSr6IyL4aiWiRHAnUewWkYsAIyL+wMPARs+GpUqUNS/BoqHW\n61pXQdP+4Ku9eJZ1SQezePSFPbw97wAA9WoFMv3JWKpU1O9GSeNOohgATMF6jOke4AdgoCeDUiWE\nMbB0DKx42hqu1xMa3673SZRxxhje+fQgw5+P48AhBwH+wmMDqjByQFWCAvWS15LInUTRwBjTx3WE\niHQAlnomJFUiGCf8PBj+eg3EBxrdDvVutF6rMu+DLw5y4JCDK9qHMf3JWBrUCfJ2SOocuJMoXgEu\ndGOcKiscGfDtnbB5Dvj4w/n3QO2rQa99L7OOpTk5ctRBtcrWuYfpT8ayal0qfbprB36lQZ6JQkTa\nAxcBlURkqMuk8lhPrFNlUeYx+LIXbP/W6ven2UCocZm3o1Je9O2vRxg0bjd1YgP58d26iAgN6gRp\nLaIUya9GEQCUs+dxfXxUMtDLk0GpYur4YZh/HcQvhYAwaPEwVGvj7aiUl+zZm8GQCXHM++4wAGGh\nvhw45KBipHb4UNrk+YkaY34FfhWRd4wxO4swJlUcpSbCp11h/18QFAkth3msgzhVvDkchlc/2M/o\nyfEcTXUSGuLD+Ier8dCdlfHz02am0sid1H9MRCYCTYDsuqQx5gqPRaWKlyM7YF5nOLzN7txvBETU\n9XZUygucTsNlt21h6ZpUAHp0rsCUMbHUqK5PmyvN3EkUHwIfA9dhXSp7J7Dfk0GpYuTABitJpMRD\nWA1oM0I79yvDfHyELheXZ1d8BtPGxtLtynBvh6SKgDuJIsoY85aIPOzSHLXK04GpYiBhJXx2NRw/\nCOH1rB5gQyp5OypVhIwxzP3mEH6+Qs+rIgAYcV8Vht5dmXKhek1LWeFOosi0/yeIyLVAPBDpuZBU\nsbDzJ/iiB2SmQsXzreamwArejkoVoX93pjNw7C5+WHKUSpF+XNE+jIgKfgQG+hCovbOUKe4kigki\nUgEYhnX/RHlgiEejUt619TP4urd1v0TV1tByqHbuV4akpzuZ+GYiT0/fy/F0Q0QFX54eWp0KYVqD\nKKsKTBTGmK/sl0eAyyH7zmxVGv09C37sb915HXMZtBgMvnr4WFYsWn6UB8buYtO/6QDc0SOSSY9F\nUzlK+2cqy/K74c4XuBmrj6fvjDHrReQ64HEgGGhRNCGqIrNqEiwebr2udbXduZ9eE19WOByGgWN3\ns+nfdBrUCeS1J2twefuwgt+oSr389gJvAbHASmCqiMQDrYCRxpjPiyI4VUSMgSWjYOWz1nD9m6BR\nH+23qQxwOg3H0w0hwT74+gqvjY9l8aoUHu1fhUDtwE/Z8ksUrYBmxhiniAQBe4HzjDEHiiY0VSSc\nDvh5EKybaSWGxn2h7g3ab1MZ8PfmNAaM2UXDOkG89VxNAC5rG8ZlbbUWoU6VX6LIMMY4AYwxx0Xk\nP00SpYwjA765A7bMBZ8AaHov1OqqSaKUSz3mYPy0vUyelUhWFmyPy+DQkSwiKmgzo8pdft+MhiKy\nzn4twHn2sADGGNPM49Epz8lMhQU9Ycf34BcCzR+wTl6rUu3Lnw8z+Mk4dsVnIAID+1Tk6WHVCS+v\nSULlLb9vR6Mii0IVreOH4LNrIeF3CChvd+7X2ttRKQ/KyjLc8vB2Pvve6sCveaNgZk6oQZsL9LJn\nVbD8OgXUjgBLo5QEq3O/pL8hKApa/Q8qNvF2VMrD/PyECmG+lAv14akh1Rl8RyXtwE+5zaOXNYjI\nVSKyWUS2icjIPOa5WUQ2iMg/IvKRJ+Mp8w7/B3MutpJEaDVoO0qTRCm2Ym0qK9amZg9PHBHNxu8a\nM+Qu7eVVnRmPNUza92G8CnQG4oBVIrLAGLPBZZ56wGNAB2PMIRGp7Kl4yryk9TCvC6QmQPma0OYx\nKFfd21EpDzicnMVjk+KZOTuJhnWCWPtlQwICfIiK0PMQ6uy49c0RkWCghjFm8xmU3QbYZoz5zy5j\nDtAd2OAyT3/gVWPMIQBjzL4zKF+5K345zL/GOjcRUd/q3C+4orejUoXMGMPsLw8x9Jk4EpOy8POD\nbp0q4HB6OzJV0hXY9CQi1wNrge/s4eYissCNsqOB3S7DcfY4V/WB+iKyVESWi8hV7oWt3LbjR/ik\nk5UkKjaDdk9okiiFtu44Tpd+2+gzdAeJSVl0aBnKnwsa8dyj0QQH6Y1z6ty4U6MYh1U7WARgjFkr\nIrULcfn1gI5ADLBYRJoaYw67ziQi9wH3AdSoUaOQFl0GbJkHX98Gzkyo2tbu3C/Y21GpQpaZabji\n9q3E7c0kMtyXFx6N5q5eUfj46HkIVTjc6mbcGHNETr0Jy7jxvj1YXYCcEGOPcxUHrDDGZALbRWQL\nVuI45XkXxpjXgdcBWrVq5c6y1bo34KcBVud+sR2h+SDt3K+UMcYgIvj7C08Pq87C5Ud54dFoKmkH\nfqqQuVMn/UdEbgN8RaSeiLwCLHPjfauAeiJSW0QCgFuBnE1Wn2PVJhCRilhNUf+5G7zKw8rn4cf7\nrCRR+1po/pAmiVIkMSmTO4btYMKre7PH9b0hirefr6VJQnmEO4niQaznZacDH2F1N17g8yiMMVnA\nYOB7YCMw1xjzj4iMF5Fu9mzfAwdEZAOwEBiu3YScA2Ng8Qj4bSQgUP9maKY9wJYWTqdh5uz9NOyy\ngQ++OMjkWfs4muLwdliqDBBj8m/JEZELjTF/FFE8BWrVqpVZvXq1t8MofpwOq6np7zdBfO3O/Xpo\nv02lxF8bjzFgzG6W2/dFXHVpeV4dF0udGlpTVG7ISqdSy5u2708xdc7m7e4car4oIlWBecDHxpj1\nZ7Mg5UFZ6fDt7dbJa58AqxZRs4smiVIgM9Pw2KQ9vPzOPhwOqFbZnymjY+h1dTiin68qIgU2PRlj\nLsd6st1+YKaI/C0ioz0emXJPRgp8fr2VJPxC4MKHtQfYUsTPD/7ckIbTCQ/2rcTG7xtz0zURmiRU\nkXKr8doYsxfr4UULgUeBJ4AJngxMuSHtoHUjXcIKq3O/C4dA1Vbejkqdo13xGTgchtqxgYgIM56K\n5chRB62aagd+yjvcueGukYiME5G/gRNXPMV4PDKVv5R4+PhSK0kEVbS65NAkUaJlZhomvZlIo64b\n6D9qFyfOH9arFaRJQnmVOzWKWcDHQFdjTLyH41HuOLQN5nWG5B0QWh3aPAoVzuoclSomfv8jhQFP\n7GbdpjQAIiv4cizNSWiIr5cjU8qNRGGMaV8UgSg37V9nde53LBHK17L6bdLO/UqsQ0eyGDkxntfn\nJAFQOzaAV8fFcvVlFbwcmVIn5ZkoRGSuMeZmu8nJ9RpafcKdt+xZCvOvhfQjENHA7twvyttRqbOU\nnu6k+fWb2BWfgb+/MPzeyowaWI2QYO2bSRUv+dUoHrb/X1cUgagCbP8OFtwIWWlQ6QJoNRwCy3s7\nKnUOAgN9uOemKH5edpTXxsfSuJ72w6WKpzwPXYwxCfbLgcaYna5/wMCiCU8BsOlj+LyblSSqtoM2\nj2uSKIGOpzsZ+3I8Hy04mD3u8QeqsuijepokVLHmTh23cy7jri7sQFQe/poJX/e2eoCNvQJaD9ce\nYEugH5ck0/SajYyftpdHno4j7bj1kAg/P9F7IlSxl985igewag51RGSdy6QwYKmnAyvzjIGVz8GS\nx63hOtdDk7u036YSZu/+TKYJCDoAACAASURBVIY+E8fsLw8B0KReEDOeqqHPiFAlSn57nY+Ab4Fn\nAdfnXR81xhzM/S2qUBgDvw6HNS8CAg1uhoa9QXTnUlI4HIaZs5N4/MV4jhx1EBwkjH2wGo/cVZmA\nAP0cVcmSX6IwxpgdIjIo5wQRidRk4SHOLPjxflg/y+rcr8mdcF537ZKjhHE4DK+8v48jRx1c07E8\n08bGUjtWO/BTJVNBNYrrgDVYl8e67qkMoHd4Fbas49YT6bbNB98AaHo/1MrtFJEqjo6mOHA4DeHl\n/QgI8OGNp2uSmJTJjV21Az9VsuWZKIwx19n/C+uxpyo/xliXv27/FvxDrSfSRV/s7aiUG4wxzP/h\nMA+Nj6PrJeV567maAFzcqpyXI1OqcLjT11MHEQm1X98uIpNFRB9cXdiOxllJwjfQukdCk0SJsCMu\nnW73/UvPQdvZk5jJ+q1pHE93ejsspQqVO2fVXgOOicgFwDDgX+B9j0ZVFhn7SWX+oVDlQu/GogqU\nmWl4fuZeGl+1ga8WJlO+nA/TxsaybG4DggL1ZLUqXdy51jLLGGNEpDswzRjzlojc4+nAlCqujqU5\naddrE39vPg7ArddFMPnxGKpV1udVq9LJnURxVEQeA+4ALhERH0B/EarMCgn2oVXTUI6lGaY/GUuX\nS/QueVW6uZMobgFuA+42xuy1z09M9GxYShUfxhjem3+Q82oEZp+gfmlUDAH+ojfOqTLBnUeh7gU+\nBCqIyHXAcWPMex6PTKliYOO2NC7vs5V+j+7kvlG7yMiwTlRXCPPVJKHKDHeueroZWAncBNwMrBCR\nXp4OTClvSjvuZPTkeC64fhO/rkyhUqQfjw2ogr+/3g+hyh53mp5GAa2NMfsARKQS8BMwz5OBKeUt\n3/16hEHjdvPf7gwA+t8SxXPDo4kM1362VNnkzjff50SSsB3AvctqlSpxUlId3PG/nSQdyuL8+lYH\nfh1a6o1zqmxzJ1F8JyLfA7Pt4VuAbzwXklJFy+EwOJ3g7y+UC/VlypgY4vZm8Mhd2tSkFLj3zOzh\nInIjcOJW4deNMfM9G5ZSRWPN+mPcP3oX3a+swJjB1QC4rVukl6NSqnjJ73kU9YBJwHnA38D/jDF7\niiowpTwp+aiDMS/HM+39/TidkJziYOT9VbUGoVQu8jvXMAv4CuiJ1YPsK0USkVIeZIzhk28O0bDr\nBqa+ux8RGHp3Zf74oqEmCaXykF/TU5gx5g379WYR+aMoAlLKU46mOLjl4e18+2syAG0vCGHGUzVo\n3jjEy5EpVbzllyiCRKQFJ59DEew6bIzRxKFKlHKhPqRnGCqE+fLc8Orcd2tFfHy0FqFUQfJLFAnA\nZJfhvS7DBrjCU0EpVVgWrzxKtcr+1KsVhIgw67kaBAX6UKWidlemlLvye3DR5UUZiFKFKelgFo++\nsIe35x2g00Vh/PhuXUSEmtH6OFKlzpTeaqpKFafT8M6nBxj+/B4OHnYQ4C9c0qocDgf46bddqbPi\n0TusReQqEdksIttEZGQ+8/UUESMirTwZjyrd/tmSRsc+W7nnsV0cPOyg00Vh/P1NI8Y+VA0/Pz0X\nodTZ8tgxloj4Aq8CnYE4YJWILDDGbMgxXxjwMLDCU7Go0u/IUQftbtpMSqqTylF+TH48htu6RSCi\nCUKpc1VgohDrl9YHqGOMGW8/j6KqMWZlAW9tA2wzxvxnlzMH6A5syDHfU8DzwPAzDV4pYwwiQoUw\nX0bcV4U9iZk8M6w6ERW0nUmpwuJO09N0oD3Q2x4+ilVTKEg0sNtlOM4el01ELgRijTFf51eQiNwn\nIqtFZPX+/fvdWLQq7fbszaDXoP/44POD2eNGDazKa+NraJJQqpC5kyjaGmMGAccBjDGHgIBzXbD9\nSNXJwLCC5jXGvG6MaWWMaVWpUqVzXbQqwbKyDFPe2UfDrhv49PvDjJ2agMNhALSZSSkPcefQK9M+\n32Ag+3kUTjfetweIdRmOscedEAacDyyyf+BVgQUi0s0Ys9qN8lUZs2pdKgPG7OKPf9IA6NG5AlPH\nxOLrqwlCKU9yJ1FMBeYDlUXkaaAXMNqN960C6olIbawEcSvWs7cBMMYcASqeGBaRRVgdD2qSUKdI\nPeZgxAvxTP9wP8ZAjeoBvPJEDN2uDPd2aEqVCe50M/6hiKwBOmF139HDGLPRjfdlichg4HvAF5hl\njPlHRMYDq40xC84xdlVG+PkKPy1LxsfH6sBv7IPVCA3x9XZYSpUZ7lz1VAM4BnzpOs4Ys6ug9xpj\nviHHQ46MMU/kMW/HgspTZce/O9MJL+9LVIQfgYE+vD+pFkGBPjRtEOzt0JQqc9xpevoa6/yEAEFA\nbWAz0MSDcakyKj3dycQ3E3l6+l76dIvkzWdrAtC6WaiXI1Oq7HKn6amp67B9SetAj0WkyqxFy4/y\nwNhdbPo3HYAsh8HhMHqyWikvO+MLzo0xf4hIW08Eo8qmfQcyGf7cHt6bb90T0aBOIK89WYPL24d5\nOTKlFLh3jmKoy6APcCEQ77GIVJmSdDCLRl03cPCwg8AAYdTAqjzavwqBgR7thkwpdQbcqVG4HtZl\nYZ2z+NQz4aiypmKkH92vDCcuIYPpT8ZSt1aQt0NSSuWQb6Kwb7QLM8b8r4jiUaVc6jEH46ft5dqO\n5bm0jXUMMv3JWAIDRO+sVqqYyjNRiIiffS9Eh6IMSJVeX/58mMFPxrErPoOvFx5h3deN8PERgrSZ\nSaliLb8axUqs8xFrRWQB8AmQemKiMeYzD8emSond8Rk8PGE38384AkCLxsHMnFBDn1etVAnhzjmK\nIOAA1jOyT9xPYQBNFCpfWVmGqe/u44kpCaQec1Iu1IcJj1Rn0O2V9EFCSpUg+SWKyvYVT+s5mSBO\nMB6NSpUKySkOnp2RSOoxJz27hvPy6Bhiqp1zx8NKqSKWX6LwBcpxaoI4QROFytXh5CyCA30IDPQh\nMtyPmRNiCQzw4drLK3g7NKXUWcovUSQYY8YXWSSqRDPGMPvLQzzydByD76jEmMHVALixa4SXI1NK\nnav8EoU2Iiu3bNl+nIFjd/PzsqMALF6Vkv2IUqVUyZdfouhUZFGoEul4upPnZybyzGt7ycg0RIb7\nMnFENP16RmmSUKoUyTNRGGMO5jVNqb37M7m09xa27rA68OvXM5KJI2KoGKnPq1aqtNFftTorVSr6\nEVstAD9f4bXxsVzWVjvwU6q00kSh3OJ0Gt74OInL24VRv3YQIsJHL9UiorwvAQF6Z7VSpZkmClWg\nvzYeY8CY3Sxfm0qni8L48d26iAhVKvp7OzSlVBHQRKHylJLqYNzUBF5+Zx8OB1Sv4s+A3hW9HZZS\nqohpolC5+vzHwzz45G7i9mbi4wMP9q3EhEeqUz7M19uhKaWKmCYKdZo9ezO49eHtpGcYWp4fwoyn\nYmnVVJ9ZrVRZpYlCAZCZafDzAxEhumoATw+tTkCAMLBPJX1mtVJlnF6uolj2Rwote2zkg89P3joz\n7N4qPNi3siYJpZQmirLs4OEs7h+9iw43b+HvzceZ/mESxmh/j0qpU5W8pqfEP+DlQG9HUfiKcAdt\njOGDzw8y7Nk97D+Yhb+/8Gj/KowaWFW73lBKnabkJQoMODK8HYTnRNT3aPGJSZn0HrKdhctTALis\nTTleGx9Lo7rBHl2uUqrkKoGJAuj8OgSW0u6rfT37YJ/wMF8S9mdSMcKPSY9F0/eGSK1FKKXyVTIT\nhW8A+JXC5icP+XFJMhc2CSEqwo/AQB8+eaUO1Sr5ExVRMj9+pVTR0pPZpVjCPquZqUu/bYx4YU/2\n+PPrB2uSUEq5TfcWpZDDYZg5O4nHJu0hOcVJcJDQoE6QPkxIKXVWNFGUMn+sP8aAJ3axat0xAK69\nvDzTxsZSK0ab6pRSZ0cTRSmyIy6dNj034XBAdBV/pj4Rww1dwrUWoZQ6Jx5NFCJyFTAF8AXeNMY8\nl2P6UOBeIAvYD9xtjNnpyZhKs1oxgdzVM4qwUF+efLgaYeW0Az+l1Lnz2MlsEfEFXgWuBhoDvUWk\ncY7Z/gRaGWOaAfOAFzwVT2m0Iy6d6/tv49cVR7PHvf50DSaPitEkoZQqNJ686qkNsM0Y858xJgOY\nA3R3ncEYs9AYc8weXA7EeDCeUiMz0/D8zL00vmoDXy1MZuTE+Oxp2syklCpsnkwU0cBul+E4e1xe\n7gG+zW2CiNwnIqtFZHUhxlciLVmdQotuGxk5MZ6044Zbr4vgs+l1vB2WUqoUKxYns0XkdqAVcFlu\n040xrwOvA7SKlTLZa92hI1kMf24Pb31yAIDzagQy/clYulxS3suRKaVKO08mij1ArMtwjD3uFCJy\nJTAKuMwYk+7BeEo0pxO++OkI/v7CyPur8NiAqgQH6f2SSinP82SiWAXUE5HaWAniVuA21xlEpAUw\nE7jKGLPPg7GUSJv+PU7tmAACA32IivDjw8m1qFE9gIbnBXk7NKVUGeKxRGGMyRKRwcD3WJfHzjLG\n/CMi44HVxpgFwESgHPCJfRJ2lzGmm6diKimOpTl5enoCE9/cx5hBVRkzuBqANjMVINPpQ1xGFMed\n/lAmGyhVmScQ5JNJTMAB/H2chVasR89RGGO+Ab7JMe4Jl9dXenL5JdF3vx5h4LjdbN9tdaWedCjL\nyxGVHHEZUYRFVqNWeHm9+kuVScYYDhxOJu4g1A7aX2jlFouT2QriEzMYMiGOT749DEDTBkHMeKoG\nF11YzsuRlRzHnf6aJFSZJiJEhZdnf1JSoZariaIY2LL9OK16bOJoqpOQYB/GPVSNIf0q4++vO7wz\nYvQ+EqVEpNCbXjVRFAP1agXSulkoocE+vDI2hprR2oGfUqr40OsrvSD5qIMhE3azZftxwDoCWDCz\nDgteP0+TRAnnGxpF87aXcH7L9lzf81YOHz6SPe2fDRu54qpuNGjWmnrnt+SpZydiXJ6V/u33P9Kq\nw+U0btGOFu0uZdiI0d5YBaVOo4miCBlj+OSbQzTsuoEp7+znofFx2dNCQ7RvptIgODiYtSt+Y/2a\n34mMiODVmW8AkJaWRrdetzHyf0PYvG4Vf638jWXLVzB95psArP9nA4MfeZQPZs1kw5/LWb10IXXP\nq12osWVl6YUR6uxo01MR+W9XOoOf3M23vyYD0K55KM8/Wt3LUZVir3romeqDDrk9a/u2rVm3/h8A\nPvp4Hh3at6XLlVcAEBISwrSXJtKxy3UMGtCfFyZPZdSIYTRsUB8AX19fHrjvntPKTElJ4cGhI1j9\nx5+ICGMfH0HPG7pRrmIMKUnWgce8z77gq2+/5503ptOv/0CCggL5c+3fdGjfls+++JK1K34jPLwC\nAPXOb8mSn7/Fx8eHAQ8OZdduq4yXJz5Dh4vanf12UqWKJgoPy8hwMunNfTz1agLH0w3h5X15bnh1\n+t9SER8fPfFaWjkcDn5euJh7+t0OwD8bNtGyRfNT5jmvTm1SUlNJTk5m/YaNDHt4UIHlPvXsRCqU\nL8/fq5cBcOjQ4QLfE7cnnmWLvsfX1xeHw8H8BV9xV98+rFi5mpo1YqlSpTK33Xkvjzz4ABd3aM+u\nXbvp2q0XG9euOIs1V6WRJgoP252QyfhpCaRnGPp0i+DFx2OoUtHf22GVfmdw5F+Y0tLSaN72EvbE\nJ9CoQX06d7q8UMv/aeGvzHnvrezhiIjwAt9z04098PW1mjZv6XUD45+dyF19+zDnk8+4pdcN2eVu\n2LQ5+z3JyUdJSUmhXDm9PFvpOQqPOHQkK/sk5Xk1A5kyJoaf3qvLB5Nra5Io5U6co9i5eR3GGF6d\nYZ2DaNyoAWv+XHvKvP9t30G50FDKly9Pk0YNWfPnX2e9XNfLgo+nHz9lWmhISPbr9u3asO3f/9i/\nP4nPv/yaG7tfD4DT6WT5rz+ydsVvrF3xG3v+26BJQmXTRFGInE7DrE+SqNvpHz74/GD2+Pt7V6LT\nRdr9RlkSEhLC1Bef58Up08jKyqLPrTexZNlyfvplEWDVPB4aNoJHhz4MwPBHHuSZFyazZes2wNpx\nz3hj1mnldr6iY3bygZNNT1UqV2Ljps04nU7mf/F1nnGJCDd0u5ahI0bRqGF9oqIiAejS6XJemf56\n9nxr//r7nNZflS6aKArJP1vS6NhnK/c8touDhx18uzjZ2yEpL2vRvBnNmjZh9tx5BAcH88UnHzLh\nuUk0aNaapq060LrlhQx+oD8AzZqez8sTn6H3nffSqHlbzm95Ef9t33FamaNH/o9Dhw9zfsv2XNDm\nYhb++hsAzz01lutuvJWLOnalWtUq+cZ1S68b+WD2XG7pdWP2uKkvPs/qP9bSrHUHGrdox4w3T09S\nquwS1+u4S4JWsWJWf/cOBEV6OxTA6sDvqWkJTHorkawsqBzlx0ujYuh9fYTeJVzENqZWp1H987wd\nhlJet3HLvzQKPfnkS7LSqdTypu37U8xZPeVMT2afgy3bj9P1rm3siMtABAbcVpFnhlUnooJuVqVU\n6aF7tHNQs3oAQYHCBY2CmTG+Bu1ahHo7JKWUKnSaKM5AVpZhxkf76X19JFERfgQG+vDdrLpEVwnA\nz0+bmZRSpZMmCjet/CuVAWN28eeGNNZuTOPNZ2sCaN9MSqlSTxNFAY4cdTDqxXimf7gfY6BG9QC6\nX1nB22EppVSR0USRB2MMH399iEeejmPv/iz8/GDo3VV4YnBV7cBPKVWmaKLIw18b0+g9ZAcAF10Y\nyoynatC0QbB3g1Jn5t8v4VjhPQ6SkEpw3vUFzvb5gq+54Zbb2bh2RXYnf4XNtRNAgHfe/4jVa/5k\n2ssT3S6jX/+BXHd1V3rd2P2s4/j2+x8ZM/4Zjh1LIzAwgCsuu5QXn59w1uWdKWMMna7uzudzP6B8\n+eJ5U+u7H8xmwnOTAOs+mDtv733aPLfcfjebt24F4PDhI4SHV2Dtit9YuWoN9w0eAljrOm7USG7o\nfh0ZGRlceU0PfvluAX5+nt+Na6Jw4XAYfH2tk9LNG4fwyF2VaVw3iLtvitIO/EqiY/uhXLXCKy8l\nwa3ZZs/9lIsvasfsuZ/y5JjHTpuelZVVJD/uwpYz7hNdo389/2MaNqiPw+Hg9bfeOevyzsY33/3A\nBU3PP6Mk4XA4svu+8rSDBw/x5NPPs3rpQkSElhd1pNu1V5/WR9fHH5y8wXHYiNFUqGCtz/lNGrF6\n6UL8/PxISNjLBW0v4fprryIgIIBOl1/Gx598Rp/eN3t8PfTObNvC349y/jUbWLzyaPa4yaNiuFd7\neVVnICUlhSXLlvPWjFeY88ln2eMXLV7CJZ2upluv3jRu0Q6Hw8Hwx8bQusMVNGvdgZlvvp39/k5X\nd+fC9pfRtNVFfPHlN2ccQ7/+A3lo6Agu6tiFOo2aM++zLwDriHTwkOE0aNaaK6/pwb79J2tba/5Y\ny2Wdr6XlRR3pen1PEhL2AtCxy3UM+d9jtOpwOVOmzThlOfl1jd6v/8Ds5YJVA8ptO4wcPY5XZ7yR\nPd+4Cc8x6aVXAJg4eWr29hn71LO5ruuHcz6h+/XXZA/3uKkPLS/qSJML25+StMpVjGHYiNFc0OZi\nfl++kg9mf0ybizvRvO0l3D94CA6HA4AHHhpKqw6X0+TC9nku80x8/+PPdO7UkcjICCIiwuncqSPf\n/fBTnvMbY5j76Xx639wTsLqCOZFMj6enn3ITb4/rr+HDjz855xjdUeYTxb4Dmdw5fAdX3LGVTf+m\nM3nWPm+HpEqwL778hqu6dKJ+vbpERUaw5o+THQH+sXYdUyY9x5a/V/PWO+9ToUIFVi39hVVLfuGN\nt99j+46dBAUFMf/j9/nj919Z+N2XDBs5mrPpPSFhbyJLfvmOrz6bw8gxTwIw/4uv2Lx1Gxv+XM57\nb77GsuUrAcjMzOTBoY8y76N3WbNsEXf37cOocSebjzIyM1i9dCHDhgw+ZRnrN2ykZYsLzjg21+1w\nS68bmfvp59nT5n76Obf0uoEffvqFrf/+x8olP7N2xW+s+XMti5csPa2spb+vOCWGWTOnsWbZIlYv\n/YWp02dy4IDV51pqaiptW7fkr5VLiIqK5ON581m68DvWrvgNX19fPpxj7XCfHjeG1UsXsm7VEn79\nbSnr/l5/2jInTp5K87aXnPb30NARp827Jz6B2JiY7OGY6Gj2xOddM/1t6TKqVKlMvbonexhYsXI1\nTS5sT9NWHZgxdXJ24ji/SWNWrfkzz7IKU8mr/xYSp9Pw1twDjJi4h0NHHAQGCKMHVWX4vfn3k6NU\nfmZ/8ikPDxoAwK039WT23E9peaH1HIo2rS6kdi3rsuofflrIuvX/MG++ddR95EgyW7f9S0x0dR5/\n4ikWL12Gj48Pe+ITSEzcR9UC+m8CTjva9PHxoXGjhiTus2oOi5cso/fNPfH19aV69WpccdmlAGze\nspX1GzbR+Tqry3GHw0G1qlWzy3LtE6owuG6HFs2bsW9/EvHxCexPSiIivAKxsTFMeXUmP/z0Cy3a\nWTGmpKSyddt/XHpxh1PKOnjoMGFhYdnDU6fPZP6CrwDYHbeHrdv+JSoqEl9fX3re0A2Anxf+ypo/\n/qL1xdZDpNLSjlO5UiUA5n46n9dnvUtWVhYJexPZsHEzzZqef8oyhw99iOFDHyrUbXLC7Lmf0vum\nnqeMa9umFf/88TsbN23mznsHcnXXKwkKCsLX15cA/wCOHj16yjbwhDKZKLbvTuf2YTtY9kcqAF0u\nDuPVcbHUrRXk5chUSXbw4CF+WfQbf6/fgIjgcDgQESY+Ox6A0NCT3X0bY3hl8vN07dzplDLeef8j\n9icdYM2yRfj7+1OrQTOOp6eftqzg4CAyMjIICAjIXnbFilHZ0wMDT97fU1CNxBhDk0YN+f3XH3Kd\n7tpNuasTXaNf0KzpadP8/PxwOp2A1RNuRkbGyfJCTy3vphu7M2/+AvYmJmYnJWMMjw1/hPvvvSvf\n2P38fHE6nfj4+LBo8RJ++mURvy/6gZCQEDp2uS57253YsVplw52338qzT409paztO3Yy6eVprFry\nCxER4fTrPzDXbT9x8tRcm3wu7XARUyc/f8q46OrVWPTbkuzhuD176HjJxbmuS1ZWFp998RVrli7M\ndXqjhg0oVy6U9f9spFXLFgCkZ6QTFOT5/VaZbHoqX86XLdvTqVrJjzlTavHd23U1SahzNm/+F9xx\n283s3PI3OzavY/e2f6hdqya/LV122rxdO1/Ba6/PIjMzE4AtW7eRmprKkSPJVK5UEX9/fxb++hs7\nd+3OdVmXXdyBD2bPBawuy+d++jmXX5b7DuiESy++iI/nzcfhcJCQsJeFi62eZxvUr8f+pCR+d2mK\n+mfDxgLXN7+u0WvVrJH9/I0FX32bvZ65uaXXDcz55FPmzV/ATfYVWF07X8Gsdz8kJSUFgD174tm3\n7/Qr2BrUq5fdy+6RI8lERIQTEhLCps1bWL5yda7L63T5pcybvyC7vIMHD7Fz5y6Sk5MJDQ2hQoXy\nJCbu49s8ziUMH/pQ9nM7XP9yJglrPTrxw08LOXToMIcOHeaHnxaednBwwk+/LKJh/XrExERnj9u+\nY2f2s8537tzFps1bqVWzBgAHDhykYlQU/v6ef8ZNmalRfL84mY5tyxEY6ENUhB8LZtahcb1gKoTp\nPRGlVkglt69Ucru8fMye+ykjhj18yriePboxe+6npzXf3HtXX3bs3MWF7S/DGEOlihX5fO4H9Ln1\nJq7v2ZumrS6i1YUt8ry8dsqkZ7n/wUeYOn0mxhj63nbrac0yOd3Q/Tp+WbSYxi3aUSM2hvZtWwMQ\nEBDAvI/e5aFhIziSnExWloMhgwfQpHGjfMtz7Rr92LE0RITrru4CQP+7+tL9pj5c0OZirurcidDQ\nvPtBa9K4EUdTUoiuXo1q1awmry5XXsHGTVto39Eqr1xoOT54eyaVK5/6GVx7dRcWLV5C3fPqcFWX\nTsx4cxaNmrelQb26tGvTKtflNW7UkAljR9Hl+htxOp34+/vz6ksTade2NS0uaEbDC9oQGxNNh3Zt\n811/d0RGRjDmseHZzVxPPP4okZHW89zvfeAhBtx7V3btYM4nn2WfxD5hybLfeW7SFPz9/fDx8WH6\nlEnZNceFv/7GtVd1OecY3VHquxnfHZ/BQ0/t5vMfj/DUI9UYPagQL5dUxYp2M172JCTspe+9D/Dj\n1/O9HUqRu/GWO3huwljq16t72jTtZtxNWVmGqe/u44kpCaQec1Iu1IdI7f5bqVKlWrWq9L+rL8nJ\nycX2hjtPyMjIoEe3a3NNEp5QKvecy/9MZcATu/hrYxoAPbuGM2VMDNFVA7wcmVKqsN3c6wZvh1Dk\nAgIC6Nvn1iJbXqlLFCvWpnLRzZsxBmrFBDBtbCzXXq6d+JUJYl0to08WVGWZMQYK+SdQ6hJFmwtC\n6HpJeVo0Dmb0oGqEBJfJC7vKpCCfTA4cTiYqvLwmC1UmGWM4cDiZIJ+8rzI7GyU+UWzdcZxHno5j\n8uMx1K8dhIjw9ZvnabcbZVBMwAHiDsL+pCQoWddoKFU4xDpgigk4UKjFlthEkZ7u5LmZiTw7Yy/p\nGYaggHjmvWqd0NckUTb5+zipHVSIvcUqpQAP33AnIleJyGYR2SYiI3OZHigiH9vTV4hILXfK/Xl5\nGs2u28i4qQmkZxju6hXFjKdqFHb4Siml8GCNQkR8gVeBzkAcsEpEFhhjNrjMdg9wyBhTV0RuBZ4H\nbsmv3O0Hw7ny3kQAGp0XxIynYrm0jWf7OVFKqbLMk01PbYBtxpj/AERkDtAdcE0U3YFx9ut5wDQR\nEZPPXYCHjgUTFAhPDKzIsH6RBAQIZKZ6Zg2UUqo0cGQUPE8+PJkoogHXjmrigJz3xGfPY4zJEpEj\nQBSQ5DqTiNwH3AcgkBniO27XpJkwaaanQi8ZjmdSPsifZG/HURzotjhJt8VJui1OOpxG9bN9b4k4\nmW2MeR14HUBEVh9INbl34lLGiMjq1AzdFqDbwpVui5N0W5wkIrn3kugGT57M3gPEugzH2ONynUdE\n/IAKQOFe16WUUuqc7aN/CQAAB6NJREFUeDJRrALqiUhtEQkAbgUW5JhnAXCn/boX8Et+5yeUUkoV\nPY81PdnnHAYD3wO+wCxjzP/bO/8YO6oqjn++QkvbLbQmqwaNWI1UbYAUaAzG8CsltSlJkbRaiQ1Z\n06ipWqNUYiJETEX8USGBaIJtbbYq8qNVSBWxIulmG+hSSLfdbqs2aAkh/qiJSFxbtMLXP+597nN5\nO29Ku+9XzyeZ7J2Zc++cOTtvztx7Z87ZL2kN8LTtrcD3gR9Kegb4G8mZ1GPdROnchoQtRglbjBK2\nGCVsMcprtkXbhRkPgiAIGksEQgqCIAgKCUcRBEEQFNKyjmKiwn+0IyVscYOkA5KGJD0m6W3N0LMR\n1LNFldwSSZbUsa9GlrGFpA/na2O/pB83WsdGUeI3co6k7ZIG8+9kUTP0nGgkbZR0WNLwOPsl6a5s\npyFJF5Vq2HbLLaTJ798D7wAmA3uBOWNkPgXcncsfAe5vtt5NtMWVwLRcXnkq2yLLnQn0AwPAvGbr\n3cTr4lxgEHh9Xn9js/Vuoi3WAStzeQ7wbLP1niBbXAZcBAyPs38R8AgpY8UlwJNl2m3VHsX/wn/Y\n/jdQCf9RzTXAplzeAsxXZyYhqGsL29ttH8mrA6RvVjqRMtcFwFdJccNeaqRyDaaMLT4OfNf2CwC2\nDzdYx0ZRxhYGKrlSZwB/pAOx3U96g3Q8rgF+4MQAMFPS2fXabVVHUSv8x1vGk7H9H6AS/qPTKGOL\nalaQnhg6kbq2yF3pt9p+uJGKNYEy18VsYLakxyUNSFrYMO0aSxlbfAVYLul54BfAqsao1nIc7/0E\naJMQHkE5JC0H5gGXN1uXZiDpdcAdQE+TVWkVTicNP11B6mX2Szrf9t+bqlVzuA7otX27pPeRvt86\nz/YrzVasHWjVHkWE/xiljC2QdBVwE7DY9r8apFujqWeLM4HzgD5Jz5LGYLd26IR2mevieWCr7WO2\nDwEHSY6j0yhjixXAAwC2dwJTgO6GaNdalLqfjKVVHUWE/xilri0kXQh8j+QkOnUcGurYwvaLtrtt\nz7I9izRfs9j2aw6G1sKU+Y08ROpNIKmbNBT1h0Yq2SDK2OI5YD6ApPeQHMWpmA5xK3B9fvvpEuBF\n23+qV6klh548ceE/2o6StlgLTAc25/n852wvbprSE0RJW5wSlLTFNmCBpAPAy8CNtjuu113SFquB\n9ZI+T5rY7unEB0tJ95IeDrrzfMwtwCQA23eT5mcWAc8AR4CPlWq3A20VBEEQnERadegpCIIgaBHC\nUQRBEASFhKMIgiAICglHEQRBEBQSjiIIgiAoJBxF0JJIelnSnqplVoHsyEk4Xq+kQ/lYu/PXu8fb\nxgZJc3L5S2P2PXGiOuZ2KnYZlvQzSTPryM/t1EipQeOI12ODlkTSiO3pJ1u2oI1e4Oe2t0haAHzb\n9gUn0N4J61SvXUmbgIO2v1Yg30OKoPuZk61LcOoQPYqgLZA0Pefa2C1pn6RXRY2VdLak/qon7kvz\n9gWSdua6myXVu4H3A+/MdW/IbQ1L+lze1iXpYUl78/ZleXufpHmSvgFMzXrck/eN5L/3Sbq6Sude\nSUslnSZpraSncp6AT5Ywy05yQDdJ783nOCjpCUnvyl8prwGWZV2WZd03StqVZWtF3w2C/6fZ8dNj\niaXWQvqSeE9eHiRFETgr7+smfVla6RGP5L+rgZty+TRS7Kdu0o2/K2//IvDlGsfrBZbm8oeAJ4GL\ngX1AF+nL9/3AhcASYH1V3Rn5bx85/0VFpyqZio7XAptyeTIpkudU4BPAzXn7GcDTwNtr6DlSdX6b\ngYV5/Szg9Fy+CvhJLvcA36mqfxuwPJdnkuI/dTX7/x1Lay8tGcIjCICjtudWViRNAm6TdBnwCulJ\n+k3An6vqPAVszLIP2d4j6XJSoprHc3iTyaQn8VqslXQzKQbQClJsoAdt/zPr8FPgUuCXwO2Svkka\nrtpxHOf1CHCnpDOAhUC/7aN5uOsCSUuz3AxSAL9DY+pPlbQnn/9vgEer5DdJOpcUomLSOMdfACyW\n9IW8PgU4J7cVBDUJRxG0Cx8F3gBcbPuYUnTYKdUCtvuzI7ka6JV0B/AC8Kjt60oc40bbWyorkubX\nErJ9UCnvxSLgVkmP2V5T5iRsvySpD/gAsIyUZAdSxrFVtrfVaeKo7bmSppFiG30auIuUrGm77Wvz\nxH/fOPUFLLH9uzL6BgHEHEXQPswADmcncSXwqrzgSrnC/2J7PbCBlBJyAHi/pMqcQ5ek2SWPuQP4\noKRpkrpIw0Y7JL0ZOGL7R6SAjLXyDh/LPZta3E8KxlbpnUC66a+s1JE0Ox+zJk4ZDT8LrNZomP1K\nuOieKtF/kIbgKmwDVil3r5QiDwdBIeEognbhHmCepH3A9cBva8hcAeyVNEh6Wr/T9l9JN857JQ2R\nhp3eXeaAtneT5i52keYsNtgeBM4HduUhoFuAW2tUXwcMVSazx/ArUnKpXzul7oTk2A4AuyUNk8LG\nF/b4sy5DpKQ83wK+ns+9ut52YE5lMpvU85iUdduf14OgkHg9NgiCICgkehRBEARBIeEogiAIgkLC\nUQRBEASFhKMIgiAICglHEQRBEBQSjiIIgiAoJBxFEARBUMh/AW0FvBl4G9QtAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_AUQ7G07eRSQ",
        "colab_type": "text"
      },
      "source": [
        "Let's have a look at the toy_example objects and understand how each object impacted the ROC curve: \n",
        "\n",
        "![Binary AUC plot explained](https://habrastorage.org/webt/zc/jr/vx/zcjrvx5bn5darmm8soa7km5du3a.jpeg)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yLScgCN0L707",
        "colab_type": "text"
      },
      "source": [
        "## AUC: Calculation with weights"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5T0xVS_-NCSM",
        "colab_type": "text"
      },
      "source": [
        "CatBoost allows us to assign a weight to each object in the dataset for AUC calculation according to [the formula above](#scrollTo=4RbdSB4EMBZs).  If no weights assigned, all weights are equal to 1 and thus AUC is proportional to the number of correctly ordered pairs. If weights assigned this property is changed. \n",
        "\n",
        "Weights are useful for unbalanced datasets. If there is a class or a group of objects with a small number of samples in the train dataset it could be reasonable to increase the weights for corresponding objects. \n",
        "\n",
        "For example if we assign weight 10 to one object it can be understood as adding 9 of the same objects to the dataset.\n",
        "\n",
        "Let's calculate AUC for an example of the wrong and right classification of one important object with weight = 10."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "749r8WnGBrV0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "toy_example['weight'] = 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RgeUlnDqBscS",
        "colab_type": "code",
        "outputId": "f52d37eb-ce97-4e4c-e625-99cfaea4eeb3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "roc_auc = catboost.utils.eval_metric(toy_example['class'], toy_example['prediction'], 'AUC', weight=toy_example['weight'])[0]\n",
        "print('ROC AUC with default weights = {0:.4f}'.format(roc_auc))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "ROC AUC with default weights = 0.7292\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LKoZ8EktAOja",
        "colab_type": "code",
        "outputId": "2ba59d08-7c11-4036-b4dc-7404ad542dfe",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 343
        }
      },
      "source": [
        "# seting weight=10 to important object with correct ordering\n",
        "toy_example.iloc[0, 2] = 10\n",
        "toy_example"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>class</th>\n",
              "      <th>prediction</th>\n",
              "      <th>weight</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>0.90</td>\n",
              "      <td>10</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>0</td>\n",
              "      <td>0.80</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>1</td>\n",
              "      <td>0.60</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>0.40</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>0</td>\n",
              "      <td>0.40</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>8</th>\n",
              "      <td>0</td>\n",
              "      <td>0.30</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>0</td>\n",
              "      <td>0.25</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>0.20</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>0</td>\n",
              "      <td>0.15</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>9</th>\n",
              "      <td>0</td>\n",
              "      <td>0.10</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   class  prediction  weight\n",
              "0      1        0.90      10\n",
              "4      0        0.80       1\n",
              "2      1        0.60       1\n",
              "1      1        0.40       1\n",
              "7      0        0.40       1\n",
              "8      0        0.30       1\n",
              "5      0        0.25       1\n",
              "3      1        0.20       1\n",
              "6      0        0.15       1\n",
              "9      0        0.10       1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RY9ni8tZ36u4",
        "colab_type": "code",
        "outputId": "be00933b-da66-4255-b21b-bb1deffe7ae6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "roc_auc = catboost.utils.eval_metric(toy_example['class'], toy_example['prediction'], 'AUC', weight=toy_example['weight'])[0]\n",
        "print('AUC: = {0:.4f}'.format(roc_auc))\n",
        "print('Important object is correctly ordered, AUC increases')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC: = 0.9167\n",
            "Important object is correctly ordered, AUC increases\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kHKDRsjXAXqa",
        "colab_type": "code",
        "outputId": "dbbe4255-c9fa-4bb4-b5c7-6b6bc85c2ced",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 343
        }
      },
      "source": [
        "# set weight=10 to important object with wrong ordering\n",
        "toy_example['weight'] = 1\n",
        "toy_example.iloc[1, 2] = 10\n",
        "toy_example"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>class</th>\n",
              "      <th>prediction</th>\n",
              "      <th>weight</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>0.90</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>0</td>\n",
              "      <td>0.80</td>\n",
              "      <td>10</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>1</td>\n",
              "      <td>0.60</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>0.40</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>0</td>\n",
              "      <td>0.40</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>8</th>\n",
              "      <td>0</td>\n",
              "      <td>0.30</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>0</td>\n",
              "      <td>0.25</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>0.20</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>0</td>\n",
              "      <td>0.15</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>9</th>\n",
              "      <td>0</td>\n",
              "      <td>0.10</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   class  prediction  weight\n",
              "0      1        0.90       1\n",
              "4      0        0.80      10\n",
              "2      1        0.60       1\n",
              "1      1        0.40       1\n",
              "7      0        0.40       1\n",
              "8      0        0.30       1\n",
              "5      0        0.25       1\n",
              "3      1        0.20       1\n",
              "6      0        0.15       1\n",
              "9      0        0.10       1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8Ikg2zJ7DU6H",
        "colab_type": "code",
        "outputId": "6efbd0f1-6796-4bfa-8af2-0cf4649ddda8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "roc_auc = catboost.utils.eval_metric(toy_example['class'], toy_example['prediction'], 'AUC', weight=toy_example['weight'])[0]\n",
        "print('AUC: = {0:.4f}'.format(roc_auc))\n",
        "print('Important object is incorrectly ordered, AUC decreases')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC: = 0.4417\n",
            "Important object is incorrectly ordered, AUC decreases\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aWMlcwx0oRPA",
        "colab_type": "text"
      },
      "source": [
        "# AUC for multiclass classification"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hvAZzaLFofpj",
        "colab_type": "text"
      },
      "source": [
        "There are two AUC metrics implemented for multiclass classification in Catboost. \n",
        "\n",
        "The first is **OneVsAll**. AUC value is calculated separately for each class according to the binary classification calculation principles. \n",
        "\n",
        "The second is **AUC$\\mu$**, which is designed to meet the following properties:\n",
        "\n",
        "* Property 1. If a model gives the correct label the highest probability \n",
        "on every example, then AUC = 1\n",
        "* Property 2. Random guessing on examples yields AUC = 0.5\n",
        "* Property 3. AUC is insensitive to class skew\n",
        "\n",
        "AUC$\\mu$ could be interpreted as an average of pairwise AUCs between the classes. Details could be found in the [article](http://proceedings.mlr.press/v97/kleiman19a/kleiman19a.pdf). \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TEeRCMDBovNt",
        "colab_type": "text"
      },
      "source": [
        "### OneVsAll AUC"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pKHS8StrozyG",
        "colab_type": "text"
      },
      "source": [
        "OneVsAll AUC in Catboost returns $n$ AUC values for $n$-class classification. The value is calculated separately for each class $k$ numbered from $0$ to $K–1$ according [to the binary classification calculation rules](#scrollTo=4RbdSB4EMBZs). The objects of class $k$ are considered positive, while all others are considered negative.\n",
        "\n",
        "Let's create a small example and calculate OneVsAll AUC for 3 classes."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oD9zGUFQeRGG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "classes = [0, 1, 1, 0, 1, 1, 1, 0, 1, 2]\n",
        "\n",
        "probas =\\\n",
        "np.array([[0.4799, 0.3517, 0.3182, 0.3625, 0.336 , 0.3034, 0.4284, 0.5497, 0.231  , 0.27 ],\n",
        "       [0.2601, 0.3052, 0.3637, 0.3742, 0.3808, 0.3995, 0.3038, 0.2258, 0.264 , 0.4581],\n",
        "       [0.2601, 0.3431, 0.3182, 0.2633, 0.2832, 0.2971, 0.2678, 0.2245,0.506 , 0.271 ]])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UsN0QWUf5QgK",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate ROC AUC for each class using binary classification rules:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RK9Pchz96ZWf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "one_vs_all_df_example = pd.DataFrame({'class_0': classes, 'class_1': classes, 'class_2': classes, 'probability_of_0': probas[0, :], 'probability_of_1': probas[1, :], 'probability_of_2': probas[2, :]})\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_0'] != 0, 'class_0'] = -1\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_0'] == 0, 'class_0'] = 1\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_0'] == -1, 'class_0'] = 0\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_1'] != 1, 'class_1'] = 0\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_1'] == 1, 'class_1'] = 1\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_2'] != 2, 'class_2'] = 0\n",
        "one_vs_all_df_example.loc[one_vs_all_df_example['class_2'] == 2, 'class_2'] = 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2cg8rXL-IFh2",
        "colab_type": "code",
        "outputId": "d340d2b1-1be4-4711-e668-f1d3c7171f6c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 343
        }
      },
      "source": [
        "one_vs_all_df_example"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>class_0</th>\n",
              "      <th>class_1</th>\n",
              "      <th>class_2</th>\n",
              "      <th>probability_of_0</th>\n",
              "      <th>probability_of_1</th>\n",
              "      <th>probability_of_2</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0.4799</td>\n",
              "      <td>0.2601</td>\n",
              "      <td>0.2601</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.3517</td>\n",
              "      <td>0.3052</td>\n",
              "      <td>0.3431</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.3182</td>\n",
              "      <td>0.3637</td>\n",
              "      <td>0.3182</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0.3625</td>\n",
              "      <td>0.3742</td>\n",
              "      <td>0.2633</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.3360</td>\n",
              "      <td>0.3808</td>\n",
              "      <td>0.2832</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.3034</td>\n",
              "      <td>0.3995</td>\n",
              "      <td>0.2971</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.4284</td>\n",
              "      <td>0.3038</td>\n",
              "      <td>0.2678</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0.5497</td>\n",
              "      <td>0.2258</td>\n",
              "      <td>0.2245</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>8</th>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.2310</td>\n",
              "      <td>0.2640</td>\n",
              "      <td>0.5060</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>9</th>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0.2700</td>\n",
              "      <td>0.4581</td>\n",
              "      <td>0.2710</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   class_0  class_1  ...  probability_of_1  probability_of_2\n",
              "0        1        0  ...            0.2601            0.2601\n",
              "1        0        1  ...            0.3052            0.3431\n",
              "2        0        1  ...            0.3637            0.3182\n",
              "3        1        0  ...            0.3742            0.2633\n",
              "4        0        1  ...            0.3808            0.2832\n",
              "5        0        1  ...            0.3995            0.2971\n",
              "6        0        1  ...            0.3038            0.2678\n",
              "7        1        0  ...            0.2258            0.2245\n",
              "8        0        1  ...            0.2640            0.5060\n",
              "9        0        0  ...            0.4581            0.2710\n",
              "\n",
              "[10 rows x 6 columns]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hPUaNmVm8Fqt",
        "colab_type": "code",
        "outputId": "c3bf2565-364d-41ae-c518-79176ec4d926",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        }
      },
      "source": [
        "roc_aucs = []\n",
        "for i in range(3):\n",
        "  roc_aucs.append(catboost.utils.eval_metric(one_vs_all_df_example['class_' + str(i)], one_vs_all_df_example['probability_of_' + str(i)], 'AUC')[0])\n",
        "  print('Binary Classification ROC AUC for class {0} = {1:.4f}'.format(i, roc_aucs[-1]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Binary Classification ROC AUC for class 0 = 0.9524\n",
            "Binary Classification ROC AUC for class 1 = 0.5833\n",
            "Binary Classification ROC AUC for class 2 = 0.4444\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mWbWg_jjIVG-",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate the same metric with OneVsAll Catboost AUC and ensure everything is right:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MniDXHvMeYFX",
        "colab_type": "code",
        "outputId": "47eceb39-d324-4f74-a8c3-50ebc8c6c186",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        }
      },
      "source": [
        "aucs = eval_metric(classes, probas, 'AUC:type=OneVsAll')\n",
        "for i in range(len(aucs)):\n",
        "  print('OneVsAll ROC AUC for class {0} = {1:.4f}'.format(i, aucs[i]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "OneVsAll ROC AUC for class 0 = 0.9524\n",
            "OneVsAll ROC AUC for class 1 = 0.5833\n",
            "OneVsAll ROC AUC for class 2 = 0.4444\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z8sJVBuKrBBD",
        "colab_type": "text"
      },
      "source": [
        "#### Visualizing ROC curves"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XLe5Ys7qGyYA",
        "colab_type": "code",
        "outputId": "72a1292e-4e6a-4f98-ca0f-754e39cd5bc1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        }
      },
      "source": [
        "plt.figure()\n",
        "lw = 2\n",
        "\n",
        "colors = ['r', 'y', 'c']\n",
        "\n",
        "for i in range(3):\n",
        "\n",
        "  fpr, tpr, _ = sklearn.metrics.roc_curve(one_vs_all_df_example['class_' + str(i)], one_vs_all_df_example['probability_of_'  + str(i)])\n",
        "  plt.plot(fpr, tpr, color=colors[i],\n",
        "          lw=lw, label='ROC curve for class {0}, area = {1:.4f}'.format(i, roc_aucs[i]), alpha=0.5)\n",
        "  plt.fill_between(fpr, tpr, y2=0, color=colors[i], alpha=0.1)\n",
        "\n",
        "plt.plot([0, 1], [0, 1], color='navy', lw=lw, linestyle='--')\n",
        "plt.xlim([0.0, 1.0])\n",
        "plt.ylim([0.0, 1.05])\n",
        "plt.xlabel('False Positive Rate')\n",
        "plt.ylabel('True Positive Rate')\n",
        "plt.title('Receiver operating characteristic curve example')\n",
        "plt.legend(loc=\"lower right\")\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEWCAYAAAB42tAoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nOzdd3QUZRfA4d9NQhoQIKEXadKrlNCx\n0hQF7AX9rKgISpPeQQREsCBVEDsKCoKCKCKgqHQUCL0Tek1CevJ+f8wkbEIakM2m3OecnOxOvTO7\nO3fmnZk7YoxBKaWUSo2bqwNQSimVvWmiUEoplSZNFEoppdKkiUIppVSaNFEopZRKkyYKpZRSadJE\n4UIislNE7nB1HK4mIjNEZFgWz3OeiIzNynk6i4g8JSK/3OC4+h3MQiIyUkS+cHUc18vD1QFkFyJy\nGCgBxAFhwM9AD2NMmLPmaYyp5axpZ1ci8izwojGmZUI3Y8wrrovItURkJHCrMabrjU7DGPMl8GUG\n5jUPOG6MGeowbp77Dqrrp0cUSd1vjCkA1AduAwa5OJ7rJiIuS/6unLcr6Tq/MTk59jzHGKN/1t3p\nh4F7HN5PBH5yeN8U+Au4BPwL3OHQzx/4BDgBXAQWO/TrCGyzx/sLqJt8nkBpIALwd+h3G3AOyGe/\nfx7YZU9/BVDeYVgDvAbsAw6lsnwPADvtOFYDNZLFMQgIsqf/CeB9HcswAPgPiMI6Sh0IHABC7Wl2\nsYetAURy9ajtkt19HjDWfn0HcBzoC5wBTgLPOcwvAFgKhAAbgbHAn2l8ri0dPrdjwLMO8/wI+MmO\ncz1Q2WG89+3hQ4DNQCuHfiOBhcAXdv8XgUDgb3s+J4GpgKfDOLWAX4ELwGlgMNAeiAZi7PXxrz1s\nIWCOPZ1gexnd7X7PAuuAKcB5u9+zCesAELvfGTu27UBtoJs9n2h7XkuTf+8BdzuuhM9uM1DuOtfr\naqwjRhzi/dPhfZLvKjAdmJRs2j8AfezXpYHvgLP28K+n8Vl7AZOAo/Y6ngH42P2WAe86DDsfmGu/\nrgysstfnOayjs8LJvuNvYn3Hr9ifTQlgub2eVgJF7GEr2MvYDWt7cBLol+y780VGtivZ6c/lAWSX\nv2Q/mLL2D+x9+30Z+0t0L9ZRWBv7fTG7/0/AN0ARIB9wu939NvsH28T+Ef7Pno9XCvNcBbzkEM87\nwAz7dSdgP9aG1gMYCvzlMKzB2gj5J/wwki1bVfsL3saOr789PU+HOHYA5exprOPqhjsjy7DNHjfh\nR/kI1g/cDXjMnncpu9+zJNuwc22iiAVG27HeC4Q7/BDn23++QE2sjVSKiQIoj/VDfsKeVgBQ32Ge\n57E28B5YG4f5DuN2tYf3wEpap7CTJ9aPPQbobC+jD9AQ60fvgbWx2AX0socviLXB6At42++bOEzr\ni2RxLwJmAvmB4sAG4GWH9RcL9LTn5UPSRNEOawNfGCtp1HBY94nrOZXv/ZtY3/tq9rj1gIDrXK+r\nST9RJH5Xgdb2Zyh2/yJYO00J35/NwHDAE6gEHATapfJ5TwGW2NMuiLVD8bbdryTW9/gu4Cl7OgXt\nfrdi/Ta8gGLAWuC9ZOvoH6zkUMaezhas34Y31m93hD1sBXsZv7Y/vzpYSe6e5J836WxXstOfywPI\nLn/2lyHM/gEY4DfsvQqsPebPkw2/AmujWQqIx96QJRtmOjAmWbc9XE0kjj/SF4FV9muxfzyt7ffL\ngRccpuGGtfEsb783wF1pLNsw4Ntk4wdj773Ycbzi0P9e4MB1LMPz6azbbUAn+/WzpJ8oIgAPh/5n\nsDbC7lgb6GoO/VI9osA6SlqUSr95wMfJlnl3GstwEahnvx4JrE1nmXslzBtrg7o1leESNxz2+xJY\nR2Y+Dt2eAH53WH9Hk00jcZ1ibQj32uvLLbX1nOx7n/Ad3JPwOaWzbGmt19WknyjucngvWEcACd/1\nl7j6O2iSwrIOAj5JYb6CtUPieFTYDIcjbOAhrN/VOaBlGsvX2fHzstfRUw7vvwOmO7zvid2KwNVE\nUd2h/0RgTvLPmzS2K+l9Bln9p+cokupsjCmItbGqDhS1u5cHHhGRSwl/WIfepbD2pC8YYy6mML3y\nQN9k45XD2ltK7jugmYiUwtrLigf+cJjO+w7TuID1wyjjMP6xNJarNHAk4Y0xJt4ePrXxjzjEmJFl\nSDJvEXlGRLY5DF+bq+syI84bY2Id3ocDBbD29jySzS+t5S6H1YySmlMpzAMAEeknIrtE5LK9DIVI\nugzJl7mqiPwoIqdEJAQY5zB8enE4Ko+1l37SYf3NxDqySHHejowxq7CavT4CzojILBHxy+C8Mxrn\n9SxPShLjN9bWcT5WMgR4kqsn5ssDpZN99wZjJdPkimEdZW52GPZnu3uCpVg7G3uMMX8mdBSREiIy\nX0SC7c/uC679vp52eB2RwvsCSQdP9ffkKK3tSraiiSIFxpg1WHtfk+xOx7Ayf2GHv/zGmPF2P38R\nKZzCpI4BbyUbz9cY83UK87wI/ILVVPMkVjOIcZjOy8mm42OM+ctxEmks0gmsLyUAIiJYP/Zgh2HK\nOby+xR4no8uQOG8RKQ/MBnpgNVsUxmrWkgzEmZ6zWM0uZVOJO7ljWO3P10VEWmE1zz2KdaRYGLjM\n1WWAa5djOrAbqGKM8cPaoCUMfwyr2SQlyadzDOuIoqjD+vYzSa9OSnMdGmM+MMY0xGqaq4rVpJTu\neGR8faU13BWsDXaCkimFmOz918DD9nenCdZOU8J8DiX77hU0xtybwjTPYW2wazkMW8hYF6ckeAur\nSbCUiDzh0H2cHVMd+7PrStLP+kak9ntylNZ2JVvRRJG694A2IlIPaw/jfhFpJyLuIuItIneISFlj\nzEmspqFpIlJERPKJSGt7GrOBV0SkiVjyi8h9IlIwlXl+BTwDPGy/TjADGCQitQBEpJCIPHIdy/It\ncJ+I3C0i+bDayqOwTqIleE1EyoqIPzAE65zLjSxDfqwf3Vk71uewjigSnAbKiojndcQPgDEmDvge\nGCkiviJSHWt9peZL4B4ReVREPEQkQETqZ2BWBbES0lnAQ0SGA+ntlRfEOnkcZsf1qkO/H7E2Tr1E\nxEtECopIE7vfaaCCiLjZy3gSa4fhXRHxExE3EaksIrdnIG5EpLH9WeXD2mhHYh2dJswrtYQF8DEw\nRkSq2J91XREJSGG4tNbrNuBB+/O5FXghvZiNMVuxNvQfAyuMMZfsXhuAUBEZICI+9m+vtog0TmEa\n8Vjf1SkiUtxeF2VEpJ39ujXwHNb35X/AhyKScERdEKvZ+bLd7c3k078Bw+x1UMue7zcpDJPqdiUT\n5p+pNFGkwhhzFvgMGG6MOYZ1Qnkw1sbjGNaXKWH9PY3Vdr4bqz29lz2NTVhtrlOx2rj3Y7XZpmYJ\nUAU4ZYz51yGWRcAEYL59aLwD6HAdy7IHay/pQ6wf5P1YlwJHOwz2FdYG6iBWs8LYG1kGY0wQ8C7W\nFUCnsU7mrXMYZBXW1VenRORcRpfBQQ+sZqBTwOdYe6NRqcRyFOvcQ1+s5rptWCdo07MCq9liL1az\nQSRpN3EB9MM6EgzF2mAlbhiMMaFYJyrvt+PeB9xp915g/z8vIlvs189gnbxNuAptIRlvjvCz53/R\njv081oURYF2tU9Nu5licwriTsXYqfsFKenOwTjgnkc56nYJ1ZdVp4FMycH+H7SusKwATd5DsHYOO\nWJerH+JqMimUyjQGYH0//7F/JyuBanbT22dY90UFG2P+sJftE/voehTQAOuo8SesnZGbtcaO5Tes\nq7quuSEyA9uVbCPhSgOVh4l1s+GLxpiVro7leonIBKCkMeZ/ro5FKRGpgJXU8iU7z5ajZbvMpVRa\nRKS63SQiIhKI1bSxyNVxKZWb6Z2RKqcpiNXcVBqreeNdrBu0lFJOok1PSiml0qRNT0oppdKU45qe\nihYtaipUqODqMJRSKkfZvHnzOWNMsfSHvFaOSxQVKlRg06ZNrg5DKaVyFBE5kv5QKdOmJ6WUUmnS\nRKGUUipNmiiUUkqlSROFUkqpNGmiUEoplSZNFEoppdLktEQhInNF5IyI7Eilv4jIByKyX0T+E5EG\nzopFKaXUjXPmEcU8rIfHp6YDVkntKlgPIp/uxFiUUirPio6Ou6nxnXbDnTFmrV1yNzWdgM/sp7j9\nIyKFRaSU/eCW3OnLL2HfPldHoZzgdPH/CPe9kCnTWpy/DofzpfS8IKWu35/z4Oyhm5uGK+/MLkPS\nh8Ect7tdkyhEpBvWUQe33HJLlgTnFPv2waVLEHdz2V1lP+HFjxN/JRqT+DC5G3fI15fY6Iibemas\nUgkKlXFn20+e+PjkS+lxzRmSI0p4GGNmAbMAGjVqlLN/P3FxMGiQq6NQme3cu8TFXaB8QM+bnpTf\nhUguxBn6F/HKhMBUXrNvXyg7d16mc2friaqmoSH4sQg63Pu2+41O05WJIpikDyAva3dTSil1nSIi\n4pj60T5mzz6Im5tQv34RKlTIj4hQtqzvTU3blZfHLgGesa9+agpcztXnJ5RSyklWrz5D+w5rmD79\nALGxhoceKkuRIp6ZNn2nHVGIyNfAHUBRETkOjADyARhjZgDLsB7Qvh8IB55zVixKKZUbnToVyZix\nO1m+/BQA1asXZOyYOjRoUCRT5+PMq56eSKe/AV5z1vyVUiq3GzFiB7+uPI2Pjzu9e1Xl2Wcr4OGR\n+Q1FOeJktlJKKUtsbHxiMhgwoDoe+YTBg2tSprSP0+apiUIppXKAkNAYJr+7h0OHrzDvk0BEhEqV\nCvDR1IZOn7cmCqWUysaMMSxbdpIxY4M4cyYKd3chKCiEWrUKZVkMmiiUUiqbOnLkCiNH7mTN2rMA\nNLitMGPG1qFGdb8sjUMThVJKZUOzZx9g8pS9REXF4+fnwYD+NXjssXK4uUmWx6KJQimlsqGIyHii\nouLp0rkMgwbVoGhR192pr4lCKaWygfPnozh46AqNG/kD8HK3SjRt4k9goOsLROqDi5RSyoXi4w3f\nfHOUe9qsofurm7l0KRoALy/3bJEkQI8olFLKZfbsCWXosO1s3nwRgJYtixIREUfhG67z6hyaKJRS\nKouFh8fywYf7mDv3ELGxhqJFvRg2tCYdO5ZCJOtPVqdHE4VSSmWx117bwpq1ZxGBrl3L069vNfz8\n8rk6rFRpolBKqSz28suVOXc+ijGja1O/fuYW8HMGTRRKKeVEsbHxfPrZYYKPRzB8eC0AmjYN4IfF\nLV1yT8SN0EShlFJO8u+/lxgydDtBQSEAPP74LVStWhAgxyQJ0EShlFKZLiQkhncm7earr45iDJQp\n48PIkbUSk0ROo4lCKaUy0dKlJxgzNohz56Lw8BBeeKESPXvciq9vzt3c5tzIlVIqG/rjz7OcOxdF\nw4ZFGDOmNtWrZW0BP2fQRKGUUjchKiqO06ejuOUWXwAGDqhB48b+PPRg2Rx1HiItWsJDKaVu0F9/\nnePe+/7ghRc3EB0dD4C/vyePPOyaKq/OoolCKaWu09lzUfTpu42uT6/n0KErAJw6FeniqJxHm56U\nUiqD4uMN8+cfZeI7uwkJicXLy40er93KSy9VxtMz9+53a6JQSqkMeuXVzaxceRqA1q2KMWpULcqX\nz+/iqJxPE4VSSmVQu7Yl+fffSwwfVpN7782eBfycQROFUkqlYuXK05w8FcHTXSsA8OCDZWjXriQF\nCuStTWfeWlqllMqA4BMRjB61k19XnsbT043bWxfnllt8EZE8lyRAE4VSSiWKiYnn008P8977ewkP\nj6NAAQ/69K5KmTI+rg7NpTRRKKUUsHXrRYYM3c7u3aEA3HtvKYYOqUnJkt4ujsz1NFEopRQwecpe\ndu8OpVw5H0aOqM2ddxZ3dUjZhiYKpVSeZIwhLCyWggWtJ8uNGlmL778/zmuvVcHHx93F0WUvufcO\nEaWUSsXBg2F0fXo9r3bfjDEGgEqVCtCvX3VNEinQIwqlVJ4RFRXHtOkHmDnzANHR8RQpko/jxyMo\nV87X1aFla5oolFJ5wh9/nmX48B0cORIOwCOPlGXggBoUKeLp4siyP6cmChFpD7wPuAMfG2PGJ+t/\nC/ApUNgeZqAxZpkzY1JK5S3GGAYM/I+FC48DUKVKAcaMqUNgY38XR5ZzOC1RiIg78BHQBjgObBSR\nJcaYIIfBhgLfGmOmi0hNYBlQwVkxKaXyHhGhbFlfvL3d6NmzCi88XylXF/BzBmceUQQC+40xBwFE\nZD7QCXBMFAZIePxTIeCEE+NRSuURQUGXOXMmijvusC5xfblbJbp0LqPnIm6QMxNFGeCYw/vjQJNk\nw4wEfhGRnkB+4J6UJiQi3YBuALfcckumB6qUyh3CwmJ57/29zJt3iCKFPfn119spXNgTLy93TRI3\nwdXHX08A84wxZYF7gc9F5JqYjDGzjDGNjDGNihUrluVBKqWyN2MMK1acol27NcydewiA+x8ojYeH\nqzdxuYMzjyiCgXIO78va3Ry9ALQHMMb8LSLeQFHgjBPjUkrlIsHB4YwYuZNVq6zNRp06hXhrbB1q\n1y7k4shyD2cmio1AFRGpiJUgHgeeTDbMUeBuYJ6I1AC8gbNOjEkplYsYY3i1+xZ27LhMgQIe9OtX\njaeeLI+7e954TkRWcVqiMMbEikgPYAXWpa9zjTE7RWQ0sMkYswToC8wWkd5YJ7afNQm3SSqlVCri\n4w1uboKIMHhQDb766ghDh9akeHEt4OcMTr2Pwr4nYlmybsMdXgcBLZwZg1Iq97h4MZqJE3cD8Pbb\ndQFo2jSApk0DXBlWrqdnepRS2Z4xhu++O06btmv45ttjLFoczMmTEa4OK8/QEh5KqWxt//5Qhg3f\nwfr1FwBo2sSfMWPqUKpU3n6YUFbSRKGUypaMMUyZspeZsw4QE2Pw9/dk8KAadOlSBhE9WZ2VNFEo\npbIlEeHU6UhiYgyPP1aO/v2rU7iwFvBzBU0USqls4/TpSC5cjKZGdauyz8ABNXj0kXI0aqQF/FxJ\nE4VSyuXi4gxffnmESe/uoWRJb35c2gpPTzf8/T3x99ck4WqaKJRSLrVjx2WGDN3O9u2XAbjlFl/C\nwmLx99dmpuxCE4VSyiVCQ2OYMmUvn31+mPh4KFXSm+HDa9G2bQk9WZ3NZDhRiIivMSbcmcEopfIG\nYwyPP/EPu3aF4O4uvPBCBd54vSoFCui+a3aU7g13ItJcRIKA3fb7eiIyzemRKaVyLRHh+ecqUq9e\nYX5Y3IIhg2tqksjGMvLJTAHaAUsAjDH/ikhrp0allMpVoqPjmTP3IO5uQrdulQF48MEydO5cRgv4\n5QAZSuHGmGPJ2gzjnBOOUiq32bDxAsOGbWffvjA8Pd3o8mBZihX1QkRwd3d1dCojMpIojolIc8CI\nSD7gDWCXc8NSSuV0Fy5EM37CLhYuPA5AhQr5GT26NsWKerk4MnW9MpIoXgHex3q0aTDwC9DdmUEp\npXIuYwwLvzvO+PG7uHgxBk9PN155pTKvvlIZLy89hMiJMpIoqhljnnLsICItgHXOCUkpldMtXhzM\nxYsxNGsWwJjRtalUqYCrQ1I3ISOJ4kOgQQa6KaXyqIiIOEJDYyhe3BsRYczo2vz33yU6ddICfrlB\nqolCRJoBzYFiItLHoZcf1hPrlFKK1avPMGLkDsqV8+Xzz5ogIlSqVECPInKRtI4oPIEC9jAFHbqH\nAA87MyilVPZ36lQkY8buZPnyUwDkz+/BxYsxWnojF0o1URhj1gBrRGSeMeZIFsaklMrG4uIMn39+\nmMlT9hIWFouvrzu9elXl2f9VwMNDH5qZG2XkHEW4iLwD1AISn1xujLnLaVEppbKl+HjD40/8zebN\nFwFo26YEw4bXokxpfdpcbpaRRPEl8A3QEetS2f8BZ50ZlFIqe3JzE1q1KsaJExGMGlmbe+4p4eqQ\nVBbISKIIMMbMEZE3HJqjNjo7sFSdOAEjR7ps9krlJcYYfvrpJO4eQof2pQB4uVslXni+Ivnza22m\nvCIjn3SM/f+kiNwHnABc9ySRuDg4f95ls79pZcu6OgKlMuTIkSsMH7GDP/44R4C/J82bFaVQoXx4\nebnjpTdX5ykZSRRjRaQQ0Bfr/gk/oJdTo0qLMTBokMtmr1RuFxUVx+zZB/lo2n6iouIpVCgffftW\no2BBPYLIq9L95I0xP9ovLwN3QuKd2UqpXOaff84zbPh2Dhy4AkCXzmUYNKgGRbU+U56W1g137sCj\nWDWefjbG7BCRjsBgwAe4LWtCVEplhbg4w/AROzhw4AqVKuVnzOjaNGtW1NVhqWwgrSOKOUA5YAPw\ngYicABoBA40xi7MiOKWUc8XHG6Ki4vHxccfd3Sq9sWHDBbp1q6QF/FSitBJFI6CuMSZeRLyBU0Bl\nY0wOPpOslEqwe08Iw4buoFLl/EwYXw+AJk0CaNIkwMWRqewmrUQRbYyJBzDGRIrIQU0SSuV84eGx\nfPDhPubOPURsrOHY8XAuX46hUKF8rg5NZVNpJYrqIvKf/VqAyvZ7AYwxpq7To1NKZarffjvNiJE7\nOXEiAhHo2rU8/fpWw89Pk4RKXVqJokaWRaGUcqrY2Hh6vr6VFSusAn41a/rx1tg61KtX2MWRqZwg\nraKAWghQqVzCw8ONggU9yJ/fnd69q/HM0+W1gJ/KMKd+U0SkvYjsEZH9IjIwlWEeFZEgEdkpIl85\nMx6l8pJt2y6ybdvFxPeDBtbglxW38/xzFTVJqOvitFst7fswPgLaAMeBjSKyxBgT5DBMFWAQ0MIY\nc1FEijsrHqXyipCQGCa+s5uvvz5K5coF+HFpKzw93ShSRJ8ToW5MhhKFiPgAtxhj9lzHtAOB/caY\ng/Y05gOdgCCHYV4CPjLGXAQwxpy5jukrpRwYY1iy9ARvvbWLc+ei8PAQ7r67BPHxxtWhqRwu3UQh\nIvcDk7CeeFdRROoDo40xD6QzahngmMP740CTZMNUteexDuvxqiONMT9nMHallO3QIauA37p15wBo\n2LAIY8fUoVq1gumMqVT6MnJEMRLr6GA1gDFmm4hUzMT5VwHuAMoCa0WkjjHmkuNAItIN6AZQo4A+\nh1cpRzEx8XTt+g8nT0VSuHA+BgyoziMPl8PNTVwdmsolMlRm3BhzWSTJly4jx7LBWCVAEpS1uzk6\nDqw3xsQAh0RkL1biSPK8C2PMLGAWQKPixfU4WimspiYRIV8+N/r2rcbf/5xn4IDqBARoAT+VuTJy\n6cNOEXkScBeRKiLyIfBXBsbbCFQRkYoi4gk8DixJNsxirKMJRKQoVlPUwYwGr1RedPZcFH36bmPq\n1P2J3R58sCzvTKynSUI5RUYSRU+s52VHAV9hlRtP93kUxphYoAewAtgFfGuM2Skio0Uk4fzGCuC8\niAQBvwNvapkQpVIWH2/46qsjtGmzmsWLg5kz9yBhYbGuDkvlARlpeqpujBkCDLneiRtjlgHLknUb\n7vDaAH3sP6VUKnbtCmHosO1s3Wqdvru9dTFGjapNgQL6MCHlfBn5lr0rIiWBhcA3xpgdTo5JKWWL\niYnnnXd288m8w8TFGYoX92L4sFp06FCSZOcNlXKadJuejDF3Yj3Z7iwwU0S2i8hQp0emlMLDQ9gZ\nFEJ8vOF/z1Tgl19u5957S2mSUFkqQ8etxphTWA8v+h3oDwwHxjozMKXyqssnIwiJMVDECxFh7Jg6\nhIbGULeuFvBTrpGRG+5qAI8BDwHngW+Avk6OS6k8JyYmnqlzDzFz8m6K1y2M+aopIkLFivldHZrK\n4zJyRDEXKzm0M8accHI8SuVJ/2y+QM8h29m+KwQAbz8PIiLi8PXVk9XK9dL9FhpjmmVFIErlRRcv\nRzN0/C7mfHUUgArlfGnSvxr+zQI0SahsI9Vvooh8a4x5VES2k/RObH3CnVKZICoqjsAOazkWHEG+\nfELvbpUZ2LMK70bEciFOCxCo7COtXZY37P8dsyIQpfIaLy93nn3sFn5fd5YPx9alRlW7gF+E3kSn\nspdUL481xpy0X3Y3xhxx/AO6Z014SuUekZFxjJ68h/mLjyd2G/Darfz6TfOrSUKpbCgjJTzapNCt\nQ2YHolRutvKPszRst4Zx7++l/5idRETGAdYjSvWeCJXdpXWO4lWsI4dKIvKfQ6+CwDpnB6ZUbnDq\nTCT9xwTx7RKrcHLNqgX5cFwdfLzdXRyZUhmX1jmKr4DlwNuA4/OuQ40xF5walVI5XFyc4eMvjzD8\nnV1cDonFx9uNIb2q8foLlfD01OdVq5wlrURhjDGHReS15D1ExF+ThVKpi4szTJt3iMshsbS/szhT\nRteh4i2+rg5LqRuS3hFFR2Az1uWxjg2pBqjkxLiUynHCrgiXPGIoXCgfnp5uTJtQlzNno+jcQWsz\nqZwt1URhjOlo/8+sx54qlSsZY/h5pQejJpSh/R07mflOfQBaNA5wcWRKZY50G0tFpIWI5LdfdxWR\nySJyi/NDUyr7O3wslAee/YXufX05fcaDoL2hRNpXNCmVW2TkrNp0IFxE6mEVAzwAfO7UqJTK5mJi\n4pnw0TZq3rGAH1cepUABw/AB51n9fUu89YomlctkpJhMrDHGiEgnYKoxZo6IvODswJTKrsIjYml6\n/w9s32Vdz/F4p8r06rmNIv6huLvruQiV+2QkUYSKyCDgaaCViLgB+ZwbllLZl6+PB43qFiU8IpZp\n41rQ9vayHDq3lRhtcVK5VEYSxWPAk8DzxphT9vmJd5wbllLZhzGGzxbso3IFP1oGlgRgyshmeOZz\nw8dHK7yq3C8jj0I9BXwJFBKRjkCkMeYzp0emVDawa99F7nzkJ57tvYZu/f8gOto6bCjk56lJQuUZ\nGbnq6VFgA/AI8CiwXkQednZgSrlSREQsQydspF6b71nz90mKBXgzqEd98uXTu6pV3pORXaIhQGNj\nzBkAESkGrAQWOjMwpVzl59+P8dqQdRw8EgrAS09VZ/ygxvgX8XZxZEq5RkYShVtCkrCdJ2OX1SqV\n44RdieHp11dz7kIktasXYcb4lrRoXNLVYSnlUhlJFD+LyArga/v9Y8Ay54WkVNaKi4snPh7y5XOj\nQP58vD+6GcdPXqH3S3W0qUkpMvbM7DdF5EGgpd1pljFmkXPDUiprbP7vLC8P+JNObcszrHcDAJ7s\ncquLo1Iqe0nreRRVgElAZYDNmAoAACAASURBVGA70M8YE5xVgSnlTCGh0Qx7ZxNTPwkiPt4QEhrN\nQD1ZrVSK0vpVzAV+BB7CqiD7YZZEpJQTGWNYsPQg1W9fwAdzdiICfbrVYcuKBzVJKJWKtJqeChpj\nZtuv94jIlqwISClnCQ2L5rFXV7F81TEAmtxWnBnjW1K/tlZ5VSotaSUKbxG5javPofBxfG+M0cSh\ncpQC+fMRFRVHIT9Pxg9qTLeuNXBz09pMSqUnrURxEpjs8P6Uw3sD3OWsoJTKLGv/OUmp4r5UqVQI\nEWHu5NZ4e7lTopg+bU6pjErrwUV3ZmUgSmWmcxci6T92PZ98s5e7W5bm1/n3IiKUL1vQ1aEpleNo\nsRqVq8THG+Z9u5c3x6znwqUoPD3daNWkJHFxBg8PbWZS6kY49TIPEWkvIntEZL+IDExjuIdExIhI\nI2fGo3K3nXsucMfDP/JC37VcuBTF3S1Ls33lQ4zo0xAPD72iSakb5bQjChFxBz4C2gDHgY0issQY\nE5RsuILAG8B6Z8Wicr/LIdE0vX8JYVdiKF7Uh8kjmvJkl8qI6FGEUjcr3UQh1i/tKaCSMWa0/TyK\nksaYDemMGgjsN8YctKczH+gEBCUbbgwwAXjzeoNXyhiDiFDIz5MB3esSfCqccQMbU6Swl6tDUyrX\nyMjx+DSgGfCE/T4U60ghPWWAYw7vj9vdEolIA6CcMeantCYkIt1EZJOIbAqPiMjArFVuF3zyCg+/\ntJIvvtuf2G3IG7cxfXxLTRJKZbKMND01McY0EJGtAMaYiyLiebMzth+pOhl4Nr1hjTGzgFkAjYoX\nNzc7b5VzxcbG89G8IIZO3ETYlRi27DjHk10q4+7ups1MSjlJRhJFjH2+wUDi8yjiMzBeMFDO4X1Z\nu1uCgkBtYLX9Ay8JLBGRB4wxmzIwfZXHbNx2llcG/smW7ecA6Ny+PB+Mbo67u56oVsqZMpIoPgAW\nAcVF5C3gYWBoBsbbCFQRkYpYCeJxrGdvA2CMuQwUTXgvIquxCg9qklBJXAmPYcBbG5j2aRDGwC1l\nCvDh2OY80La8q0NTKk/ISJnxL0VkM3A3VvmOzsaYXRkYL1ZEegArAHdgrjFmp4iMBjYZY5bcZOwq\nj/Bwd2PlH8G4uQl9utVhRJ8G5PfN5+qwlMozMnLV0y1AOLDUsZsx5mh64xpjlpHsIUfGmOGpDHtH\netNTeceBwyEU9vMkwN8bLy93Pv/gTry93KlTw9/VoSmV52Sk6eknrPMTAngDFYE9QC0nxqXyqKio\nON6Z/i9vfbiNp7rcyseTWgPQuH4xF0emVN6VkaanOo7v7UtauzstIpVnrf7rBK8OWsfu/ZcA6wqn\nuLh4PVmtlItd953ZxpgtItLEGcGovOnMuQjeHLOezxbuA6Ba5UJMf7sld7Yo7eLIlFKQsXMUfRze\nugENgBNOi0jlKecuRFLj9gVcuBSFl5c7Q3rWp3/3enh5ubs6NKWULSNHFI51mWOxzll855xwVF5T\n1N+bTu3Kc/zkFaaNa8GtFQu5OiSlVDJpJgr7RruCxph+WRSPyuWuhMcwesoW7rv7Flo3LQXAtHEt\n8PJy1zurlcqmUk0UIuJh3wvRIisDUrnX0l+O0GPoXxwNDuOn347x38qHcHMTvL31sShKZWdp/UI3\nYJ2P2CYiS4AFwJWEnsaY750cm3Ky0yHfEx59yOnzOXFKGD3Bm19WWTfJ1aoex9hhxzhyYXI6Yyql\nsoOM7Mp5A+exnpGdcD+FATRR5HDh0YeIjQvBEOuU6cfGwufz/fhgemHCI9zw9Y2nV/eLPPVoKB4e\nEBPnlNm6jJeHXqWlcqe0EkVx+4qnHVxNEAm0gmsuYYilfEBPp0z7wqVoPp73O+ER0XTpUIp3RtSi\nbCkfp8xLKeU8aSUKd6AASRNEAk0UKkWXLsfg4+2Gl5c7/oU9mTquLl6ebnS4u4SrQ1NK3aC0EsVJ\nY8zoLItE5WjGGL75IZj+Y3byyjMVGfxGVQA6dyjl4siUUjcrrUSh1yqqDNl3MIzXh27n93XWcyL+\n3HA+8RGlSqmcL61EcXeWRaFypMjIOCbN2M/Ej/YTHR2Pf+F8jBtck2ceKadJQqlcJNVEYYy5kJWB\nqJzl1JlI7nn0L/Yfsq6YfvqRcrw9uAZF/fV51UrlNnqnk7ohJYp5UbaUDx7uwgdv1aF106Lpj6SU\nypE0UagMiY83zPn6CHc0K0qVSgUQET79oAFFCuXD01PLgCuVm2miUOn6L+gyPQdvZ/3Wi9zZoijL\nvmyKiFCimDYzKZUXaKJQqQq7EsvYKXv4cO4h4uIMpUt489JT5V0dllIqi2miUClasuIkvUfsIPhk\nJG5u0P3ZiozsVw2/gvlcHZpSKotpolDXCD4VwdM9txAVFU+DOoX4cFxdGtYt7OqwlFIuoolCARAT\nE4+HhyAilCnpw6h+1fHM58bLz1TA3V3viVAqL9PLVRR/b7pAs45r+WrR8cRuvbpVpvtzFTVJKKU0\nUeRlly7D8LEB3PnQOnbsDmXWZ0cwRus9KqWS0qanPMgYwxff7af3yAKcv+hGvnxCn5dvZWDPKk4p\nvREbbzgV7k5UnB6dZMR94kucB4RdSX9YpZJzczN4e8XhlomHAZoo8pjTZ8N5ovsqfv/rJOBGYMNI\nZk1oT/UqBZ02z1Ph7vj5F8O/cCGtAZUBJ+MMsQZKeui6UtfHGMPFi5e5cOEMvj6Z92QwTRR5TGE/\nL06eiaCovzcDel/k/ntPU6Go85IEQFScaJJQKguICEWKFOLcubOZOl1NFHnAr2uP06B2UQL8vfHy\ncmfBzLspVdyXkPiPsuxxpJoklMoazvit6cnsXOzkaauZqe0TyxkwbkNi99rV/Qnw93ZhZEqpnEQT\nRS4UFxfPtHlBVL/9W+b/cAAfb3eqVS6Up69oyufrR4PAZtRt0JgHHnyES5cuJfbbGRTEPe3upUad\n26hWqx5jx41Psq6Wr/iFwOatqF2/IQ2bNKffgEGuWIQ0Pf30szRq1IQPPpiaqdOtWrUm586dy9Rp\nJpg4cRI1a9alTp3b+PXXlU6Zh7Nt2bKVhg0DqVmzLn369EvxN3bx4kUeffRxGjVqQsuWt7Nz587E\nflWr1qRhw0ACA5vRvHmrxO6DBg2hbt3baNSoCY8++niS7yvA0aPHCAgowZQp7ztv4Rxooshltmw/\nR7MHlvDakHWEhMZw393lCFr9CG++Wi9PN//4+PiwZcPf/LdlI/5FijBtxiwAIiIi6PzQY/Tv15dd\n27eydePf/PXPeqbPtPrv2LmT13v15bNPPmbHts1s+OsPKleulKmxxcbG3tT4p06dZvPmLWzatJ7X\nX++RJfO8Wbt27WLBgoVs3bqRJUsW8frrvYmLu/l20Kxertdf78W0aVPZufNf9u8/wC+//HrNMBMn\nTqJu3bps2rSeOXNm0bdv/yT9V6xYxoYNf/PXX38kdrvrrrvYsmUjmzatp0qVKrzzzrtJxhkwYCDt\n2rVxzkKlQM9R5CKHj4USeN9i4uIMZUrm54MxzejSoUK2ShAy5i2nTNcMG5LhYZs2DWT79h0AfDX/\nW5o3a0rbNtYDHX19fflwyrvc1bYD3V95mXfefY9BA96kerVqALi7u/Nqt5eumWZYWBiv9+7H5i1b\nEBGGDRnEQ1064xdQgpDzpwFY+P0iflr2M598PJPnXnwZb28vtv37H82bNWXR4iVs2fAXhQtbpVLu\nqFefNat+wc3NjZ493+DYMetmyHfemUDz5s2SzLtjxwc4ceIEgYHNmDx5EgULFqRnzzcIDw+nUqWK\nzJw5nSJFitCmTXvq1avLX3/9zaOPPkKvXq8nib93735sseMfMmQQXbp0TjKfRx55nOPHjxMZGclr\nr3XnxRefJy4ujpdf7p443v/+9wyvv96Djz6axuzZc/Dw8KBGjep8/vmnSaa1dOlPPPLIw3h5eVGx\nYgUqV67Exo2baNq0Saqf21tvvc2yZcuJiIigadMmfPTRh4jINcvVunUr+vcfyJUrVwgICGD27JmU\nKlWSOXM+Ye7cT4iOjqZy5UrMnfsxvr6+6X1dUnXy5ClCQkJo0iQQgKeeeoIlS5bSrl3bJMPt2rWb\nfv36AFCtWjWOHDnK6dOnKVGiRKrTbtPm6gNGAwMb8/33ixPfL1mylAoVKtxU7NfLqYlCRNoD7wPu\nwMfGmPHJ+vcBXgRigbPA88aYI86MKTerUK4gzz1WlYL58zGqX0MKFvB0dUjZTlxcHKt+X83zz/4P\ngKBdu2jYoH6SYSpXrkTYlSuEhISwMyiIPg4b1NSMfXsChQr58e9m61zQxYsX0x3nePAJ/lz9G+7u\n7sTFxbHoh6U897+n2bJxI2XKlaNEiRI888xz9OzZgxYtmnP06DHuv78T//67Jcl0Fi78lgcffJgN\nG/4GoFGjJkyePInWrVsxatQY3nrrbSZNmghAdHR0kj3XBG/b8W9OI/6ZM6fh7+9PREQELVq0pkuX\nThw5cpQTJ06wZctGgMQmkkmTJrN79068vLyuaTYB7MQWmPi+TJkynDhxIs319eqrLzNkiNXs99xz\nL7Js2XLuu+/eJMsVExNDmzbtWbBgPsWKFWPBgoWMGDGKWbOm07nzA7zwwnMAjBgxinnzPqV791eT\nzGP16jX07z/wmnn7+vqyevVv1yxDmTJlki3DyWvGrVOnDj/8sISWLVuwceMmjh49SnDwCUqUKIGI\n0LFjJ0SEF154nhdffP6a8T/99HMefvghwEro7747hZ9+WpJlzU7gxEQhIu7AR0Ab4DiwUUSWGGOC\nHAbbCjQyxoSLyKvAROAxZ8WU2xw+FkrPoX/R75W63N6sFACzJrbKVkcQyV3Pnn9mioiIoEFgM4JP\nnKBGtWq0ufuuTJ3+b6t+56vP5yW+L1KkSLrjPPxgF9zd3QF49OGHGDNuPM/972mWLPiOjg89CMDv\nv//O7t27E8cJDQ0lLCyMAgUKpDjNy5cvc+nSZVq3ttq7u3Z9iqeeevrqPO0NTnKrVv3O5+nE/9FH\n01myZCkAx48Hs3//AapWrcKhQ4fp3bsvHTq05557rD3h2rVr8+yzz3P//ffzwAMd010XGbFmzVom\nT36P8PBwLl68SM2aNRITRcJy7d27l507g7jvvgcAa8egZMmSAOzcGcTIkaO5fPkyYWFXkuy1J7jj\njtsTE25mefPNPvTt25/AwGbUqlWL+vXrJX7uq1b9SpkypTlz5gz33fcA1apVpVWrlonjjh8/EQ8P\nd554wtosjh07jp49X0v183cWZx5RBAL7jTEHAURkPtAJSEwUxpjfHYb/B+jqxHhyjZiYeCbP+o9R\nk7cQERnHuQuR/L20E6CXoaYm4RxFeHg4HTp2YtqMmfR8rTs1qlfnjz/XJRn24MFDFMifHz8/P2rW\nqMHmLVupV7fODc3X8fOIjIxK0i9//qtNB82aNuHAgYOcPXuWFT/+yJL+bwIQHx/P2rW/4+2dOVep\n5c+f/4bGW7NmLatWrWbNmlX4+vrSpk17IiMjKVKkCBs3/s2vv65k9uw5LFz4PbNmTWfx4u/4448/\nWbZsORMmTGTz5g14eFzd3JQuXZrjx6/WFgsODqZ06dKpzj8yMpI33ujNunV/UK5cWcaMeYvIyMhr\nlssYQ82aNVizZtU103jppVdYsGA+devW4bPPvmDt2muPrK7niKJ06dIEBwcnW4ZS14zr5+fH7Nkz\nEuOrVq0WFStWAKBMGWuZixcvzgMP3M+mTZsTE8Vnn33B8uU/s3z5j4nfow0bNvL994sZPHgYly9f\nxs3NDW9vL1599ZXUVl2mcObJ7DLAMYf3x+1uqXkBWJ5SDxHpJiKbRGRTeEREJoaY8/y54RS3tfue\ngeM2EhEZx+OdKvP9x1l3Uiun8/X15b3Jk5j83ofExsby1BOPse6vv1n5m7XPEhERwRt93+TNvr0A\n6NenF+MnTmLvvn2AteGeMfvja6Z7z913JZ4gh6tNNyWKF2fX7t3Ex8ezeMmSVOMSETp3up++/Qdx\na7VqFAkIAODuu+9m2rQZicP9++9/aS5foUKFKFKkMH/aye+rr75OsoeamrvvvosZKcSfICQkhCJF\nCuPr68uePXvYsMFqajp37hzx8fF06dKZkSOHsW3bNuLj4zl27Dh33HE7b701hpCQEMLCwpJMr2PH\ne1mwYCFRUVEcOnSY/fsP0LhxIwDat7+P4OCkzVAJSaFo0QDCwsJYtGgxKalatSpnz57jn3/WAxAT\nE0NQkLVvGhYWSsmSJYiJiWH+/G9SHD/hiCL5X/IkAVCqVEn8/PxYv34Dxhi+/PJr7r//2qOnS5cu\nER0dDcDcufNo2bIFfn5+XLlyhdDQUACuXLnCb7+tolatmgD88suvTJ48hYULv0lyLmLVql/ZuzeI\nvXuD6NGjO/3793N6koBscjJbRLoCjYDbU+pvjJkFzAJoVLx4nrzG8+KlKN4cu545X+8BoHIFP6aN\na0Hb28u6OLKc57b69ahTpzZff7OAp596gkUL5/NG73707NWHuLg4uj75OK/ZP766dWozedIEnnrm\nOcLDwxER7ru3wzXTHDKwPz3e6EPdBo1xd3dn2JBBPNi5E+PGjuKBLo9QrFhRGja4jbA0Cjg9+vBD\nNGnRmikzryaGyZPfoVevPjRq1ITY2FhatmzB1KkfpLl8H388K/FkdsWKFZk1a3q662TgwP688UYf\nGtjxDxkyiM6dOyX2b9u2DbNnz6FevQZUrVqVwMDGAJw4cZJu3V4hPj4egDFjRhEXF8dzz71ISMhl\njDF07/5q4kn6BDVr1uShhx6kfv1GeHh48P77k3F3dyc+Pp4DBw7i75+06atw4cI899yzNGgQSIkS\nJWjYsGGKy+Hp6cnXX39Bnz79CAkJITY2lh49XqNmzZqMGDGMVq3upFixojRu3IjQ0LAUp3E93n9/\nCi+99DIREZG0a9cm8UT2bHtn4qWXXmT37j28+OLLiAg1a1ZnxoxpAJw+fYbHHnsCsK7WeuyxR2nb\n1trp69WrL1FRUYlNaIGBjdP93J1JnHVtvYg0A0YaY9rZ7wcBGGPeTjbcPcCHwO3GmDPpTbdR8eJm\n07ZtTog4ezt/IZLqty/gcmg0A1+rx6Ae9fHxubk8f+jcu8TEXaB8QM9MijJlBy67U73qrU6dR26S\nl2s97dy5k08//ZyJE8enP7BK1d69+yiQP+mlwnXqtjgcFhZV8Uam58wjio1AFRGpCAQDjwNPOg4g\nIrcBM4H2GUkSec3u/ZeoWK4gXl7uBPh78+XUO7mlTAGq36pPm1O5U61atTRJZENOO0dhjIkFegAr\ngF3At8aYnSIyWkQesAd7BygALBCRbSKSeiNuHhIeEcuQ8Rupe893TJz2b2L3treX1SShlMpyTj1H\nYYxZBixL1m24w+t7nDn/nOjn34/RffA6Dh21TnKduxiZzhhKKeVc2eJktoITp67Qa8TfLPjxEAB1\navgz4+2WNG+c+t2bSimVFTRRZAN7D1yi0b2LCQ2LwdfHg5F9G9DrxTrky6eluJRSrqeJIhuoUqkQ\njesVI7+vBx+ObU75ss59kJBSSl0P3WV1gZDQaHoN/5u9B6waOCLCknltWTKvnSYJJ9Ey4zfGWWXG\nz58/T9u2HQgIKEGvXn0yffpZ5dChw7RqdQc1a9ala9dnEm+sc3T48BEKFy5KYGAzAgOb0aPH1dph\n33zzLQ0bBtKoURPuv79z4roeOXI0jRo1ITCwGffd90BiDamlS39M7N68eSvWrfsrS5ZTE0UWMsaw\nYOlBqt++gPfn7OD14VdryuT3zefCyHI/LTOeufO8Wd7e3owYMYzx4zO3mnBWL9fQocPo2fM1goL+\no3Dhwsyb92mKw1WqVDHxLu+EG+diY2Pp168/K1YsY9Om9dSpU5vp02cC0KdPLzZtWs+GDX9z773t\nGTfOuv3szjvvYOPGf9iw4W9mzpzOq6++liXLqU1PWeTgkRB6DP2L5ausqiZNGxRnwuDAdMbKfQ4f\nc06Z8QrltMx4Tioznj9/flq0aM6BAwcz/LmlVib8RXtd/vvvfzRr1pSXX+5Gr159OHfuHD4+Pkyf\nPpVq1arx00/LGD9+ItHR0fj7+zNv3pw0S32nxxjD6tVr+PTTTwCrAOPYsePolsL3I7XxjTFcuRJO\nQIAhJCSESpWsnRA/P7/E4a5cCU+s9eRYDPDKlStZVttNE4WTRUfHMWnGf4x5fyuRkXEULuTJ+EGB\nvPRUddzc8t6dt66mZcazR5nxG5FWmfDg4BOsttdl+/b3MXXq+9x6661s2LCR11/vzYoVy2jevBlr\n1/6OiDB37jwmT36PCROSFIpg7969dO36vxTn/8svy5OUIjl//jyFChVOLHaYVqn0w4eP0KRJcwoW\nLMjIkcNp2bIF+fLl44MP3qNRoybkz+9L5cqVef/9KYnjDB8+ki+//JpChfxYseLqXQY//LCEYcNG\ncPbsORYtWngDa/L6aaJwsmMnrjD6va1ERcXx1IO38u7wJpQolnUPHMlurmfPPzNpmXF7njm4zHha\nZcIftNdlWFgY//yzniefvLrMUVFW1d7g4GC6dv0fp06dIjo6hgoVyl8zj6pVq2Z6mfFSpUqyb98u\nAgIC2LJlK4888jhbt27Ex8eHWbM+5p9/1lGpUkV69+7LxImTGDRoAACjR49k9OiRTJw4ienTZzJ8\n+FAAOnV6gE6dHuCPP/5k1KgxLF/+Y6bGmxI9R+EEFy9FJZ4MrVzBj/dHNWPl/Hv54sM783SScKWE\ncxSH9u7CGMO0GVZbcI3q1dm8JWntsJTKjN+oGy0z3v4Bq3hBQpnxhPbtgwf33dSzCDKjzPjGjf9Q\nr17dJGXGW7duxezZc3jlFavNfPHi73j55W5s27aNFi1aZ8q5g5deeoX33pvM5s0bGDJkUJL1mbAu\n4+PjKVy4UJLKrwlHYL179+PVV19m8+YNTJ36fpIy5Qn27t2beNI5+V/yI6OAgAAuX76UuGyplUr3\n8vIiwK4G3KDBbVSqVJF9+/YnVgKuXLkSIsJDDz2YWPXW0eOPP8bixT9c071Vq5YcOnTYac80d6SJ\nIhPFxxvmzt/DrS2+4Yvv9id2f/npGtzdKq0K6yqraJnxlGV1mfG0PP/8S2zcuOma7hkpE+7n50eF\nChX47rvvAes8wH//bU9choQN+RdffJXi+AlHFCn9Ja+AKyLcfntrvv9+kT3NL7n//vuumebZs2cT\nnwd+8OAhDhw4QMWKFShdujS7d+/m7NmzAPz22yqqV7fOhe3ff3X78eOPP1KtWlUADhw4kLgTunXr\nNqKjoxKTkDNposgkO/dc4I6Hf+SFvmu5cCmK5b8fS38k5RKOZcZ9fHxYtHA+48ZPoEad26jXsAmN\nGzZIscx4rXoNqNugMYcOHb5mmkMG9ufixUvUbdCY2xo35fc1awESy4y3vONuStlPWkvNow8/xJdf\nz+cBu9kJrDLjW7ZsoVGjJtSv3zCxfHVaPv54FoMHD6VRoyb89992Bg++9kE8yQ2042/QoDGNGzdl\njR1/grZt2xAbG0u9eg0YOnREkjLjbdt2IDCwGc8992KSMuMNGwbSpEnzFMuMg3Xp7YABg/j88y+p\nXLkqu3btAmDHjh2UKnXtA4ASyoTfeec9iRvOlHzyyRzmzfuMxo2bctttjVi61GqaGTp0ME8++TTN\nmrWkaNHM2biOHTuGDz6YSs2adblw4QLP2ue+fvzxJ0aNGgPAn3+uS7yk9cknu/Lhh+/j7+9P6dKl\nGDJkEPfc0y7xs+rfv58d63AaNGhMo0ZNWLlyFZMmvQPAokU/0KBBYwIDm9GrVx8+//zTLDmh7bQy\n486S3cqMh0fEMua9LUya8R+xsYbiRX2YMrIpT3SunO2fNqdlxrOnvFxmPCQkhFde6c5XX33h6lBy\ntJxUZjzX23vgEu2eWs7hY2GIwCtP12DcwMYUKezl6tCUypH8/Pw0SWRDmihuQvmyBfH28qBeTX9m\njG9J04ZawE8plftoorgOsbHxzPh8F090qkyAvzdeXu78/GV7ypTMj4eHnu5RSuVOmigyaMPWM7wy\n8E+27jjPtp3n+XhSawCtzaSUyvU0UaTjckg0QyZsZNqnQRgDt5QpQKe2196oo5RSuZUmilQYY/hm\nyUF6j/ybU2ci8PAQ+nSrw/DeDbSAn1IqT9GG9VT8u/MCT3RfxakzETRvVIItPz/IhCFNNEnkUFpm\n/MY4q8z4ypWraNasJQ0bBtKsWUt+/311ps8jK2SkzHiCo0ePERBQgilT3k/SPS4ujiZNmtOly8PX\njNOnTz8CAq69SGbRosV4exdg8+Yt1/RzBk0UDuLi4hNf168dQO+XajP7nVb8seh+6tTwd2Fk6mZp\nmfHMnefNKlo0gO++W8DmzRv4+OOZvPBCxiqupie7lhkHGDBgIO3atbmm+9Sp06hmVyd2tHnzFi5e\nvLagYmhoKFOnTku86TEraNOT7fd1J+g+eB0zJ7SkdVPrrtDJI5ulM5a6XqOOBTtluiPKZbxEipYZ\nd32Z8fr16yW+rlmzJhERkURFReHllfo9SDm5zPiSJUupUKECvr5Ja70dPx7M8uU/M2DAm0mOBuPi\n4hg0aAiffvpJYiHGBKNGjaFfvz5MnvzeDcd+vfJ8ojhzLoI3x6zns4VWLZ/Js7YnJgqV+2iZ8exX\nZnzRosXUr18vzSQBObfMeFhYGO++O4WfflpyTbPTm2/2Z9y4sYSGhibpPn36DDp2vI9SpZKWfdm6\ndRvHjx+nQ4f2miiyQny8Yc7XexgwbgMXL0Xh5eXO0Nfr8+ar9dIfWd2w69nzz0xaZtyeZzYrMx4U\nFMSQIcP58cdrq6Mml1PLjI8dO46ePV+75jNbtmw5xYoVo0GD25LU1jpx4iTffbeYX39dnmT4+Ph4\n+vcfyOzZMzM1vozIk4ni0NEQuvZczV+brCaBtreX4aO3WnBrxUIujkw5S8I5ivDwcDp07MS0GTPp\n+Vp3alSvzh92pdUEE6rRaAAADAdJREFUKZUZr1e3zg3N90bLjC/p/yZwtcy4t7f3Dc0/ucwoM+7r\n60ubNu2TlBn/9deVzJ49h4ULv2fWrOksXvwdf/zxJ8uWLWfChIls3rwhcc87wfHjwTz66JPMmTMr\nQ+d9XnrpFRYsmE/dunX47LMvWLv26pFRSmXGk+vdux9vvNGTjh3vY82atYwdO+6aYa7niMKxzLiH\nh0eqZcY3bNjI998vZvDgYVy+fBk3Nze8vb0IDj7JTz8t4+effyEqKpKQkFCeffYFHnvsEQ4ePEDN\nmnUBCA8Pp2bNuvz99x8EBQXRtm0HAE6fPs3DDz/KwoXf0rBhg3TX383Ikyez/Qp4svfgZUoW92H+\ntLv4+csOmiTyCC0znrKsLjN+6dIlunR5iLFjR11zziW3lRlftepX9u4NYu/eIHr06E7//7d370FW\n1nUcx9+fXZbLgiwqVuYlLKEkdUSJNDNxJEScgRxIsBwHYzIpdbxRTTJKSIh5mdHBEUFpoRw1IZ0t\nL2QGQQoIcllhU+KiCKUwLaIILsvy7Y/fb9kjLOc8wJ7LHr6vmWd4nnN+z3O+58vZ8zvP8zvn+/v5\nbYwadR3jx/+atWtXs3p1DTNmVNK374VUVj7OpZcO4N131+3dp7y8nJqaaioqKti0acPe2/v0+UZO\nOgk4gjqK2XPfo64u1IQ/9pj2VP2uP2/94wqGDS78Kq+uZXmZ8f3lusz4I488ytq165gwYeLeiYE2\nb94MFF+Z8WJQ9GXG39u0nRvveI3nXnqXu0afw5ibst/7thZeZrwweZlxLzN+uLzMeEK7d+/hocdX\ncsd9b/DJjt106ljGMV1a5jqvcy47vMx4YSrKjmLhGx9w3S//yYqaWgCGDDyFB8edxwnHH9pAnnPO\nHcmKrqNYtHQz3xpchRl0O6kTk8afz2X9Ts53WEc8M/OxIOdyIBvDCUXXUfTpdRyX9D2RXl/vypib\nelHeoeieYqvTrtSo/XAbx3Sp8M7CuSwyM7Zu3UZJSct2Fq3+XfTf67Zx89gFPHDnufT4Shck8fyM\nAZSU+BtSofhCeQPv125hy5aWLy5XjLbtMRqAj46Y7yS6llRSYrRv19Cix2y1HUVdXQMTH17O3ZNW\nUFfXQPt2bZg5tR+AdxIFpk2JOLHTnswNHQB31X5KbYMx+mife90Vhqx+ZpE0QNLbktZI2u/L3JLa\nSXo63r9IUrckx31l/ibO7DeLsfcvpa6ugWuG9WDyPZl/VOScc+7gZe2MQlIp8DDwXWAjsFhSlZnV\npDQbCWw1s1MlDQfuAYalO+76j0rpN/wFAE7r3oXJE7/tRfyccy6LsnnpqQ+wxszWAUh6ChgMpHYU\ng4GxcX0mMEmSLM2wfe0uUdoW+vyoE2f/oB2zypYwa0N2nkDx68Ee20lF7af5DsQ5V8Cy2VGcALyX\nsr0R+OaB2pjZbknbgGOBz4x6SroWuBZAUN++ZPyG6kqorsxO4K1F/e49ncvalHx0WAcRSLT6QZ1d\n9Xs6ty07zFwUEJM0g0P7ilh9fcNRZWWlH2duWfw8F0127KhPX0MmjVYxmG1mU4ApAJKWbN9Z3zvP\nIRUESUvq6hs8F8Rc7PJcQMxF3W7PBZ6LVJL2r7SYUDYHszcBJ6Vsnxhva7aNpDZABfC/LMbknHPu\nIGWzo1gMdJd0iqS2wHBg3zrLVUBj8fehwN/TjU8455zLvaxdeopjDtcDs4FSYJqZrZI0DlhiZlXA\n48DvJa0BagmdSSZTMjc5YngumngumngumngumhxyLlpdmXHnnHO55UUCnHPOpeUdhXPOubQKtqPI\nVvmP1ihBLm6RVCOpWtIrkr6UjzhzIVMuUtoNkWSSivarkUlyIemK+NpYJan5iaKLQIK/kZMlzZG0\nLP6dDMxHnNkmaZqkzZJWHuB+SXoo5qlaUrIpP82s4BbC4Pda4MtAW2AF0HOfNj8FJsf14cDT+Y47\nj7m4CCiP66OO5FzEdkcB84CFQO98x53H10V3YBlwdNz+XL7jzmMupgCj4npP4J18x52lXHwHOBtY\neYD7BwIvAgLOBRYlOW6hnlHsLf9hZruAxvIfqQYD0+P6TOBiFedkBxlzYWZzzGxH3FxI+M1KMUry\nugC4i1A3rJhrkyTJxY+Bh81sK4CZbc5xjLmSJBcGdI7rFcB/chhfzpjZPMI3SA9kMDDDgoVAF0kZ\ni+UVakfRXPmPEw7Uxsx2A43lP4pNklykGkn4xFCMMuYinkqfZGbP5zKwPEjyuugB9JD0qqSFkgbk\nLLrcSpKLscBVkjYCLwA35Ca0gnOw7ydAKynh4ZKRdBXQG7gw37Hkg6QS4AFgRJ5DKRRtCJef+hLO\nMudJOsPMPsxrVPlxJVBpZvdLOo/w+63TzcwnSkmgUM8ovPxHkyS5QFI/4HZgkJnV5Si2XMuUi6OA\n04G5kt4hXIOtKtIB7SSvi41AlZnVm9l6YDWh4yg2SXIxEvgjgJktANoDXXMSXWFJ9H6yr0LtKLz8\nR5OMuZDUC3iU0EkU63VoyJALM9tmZl3NrJuZdSOM1wwys0MuhlbAkvyNPEc4m0BSV8KlqHW5DDJH\nkuRiA3AxgKTTCB3FlpxGWRiqgKvjt5/OBbaZ2X8z7VSQl54se+U/Wp2EubgX6AQ8E8fzN5jZoLwF\nnSUJc3FESJiL2UB/STVAAzDazIrurDthLm4Fpkq6mTCwPaIYP1hKepLw4aBrHI+5EygDMLPJhPGZ\ngcAaYAdwTaLjFmGunHPOtaBCvfTknHOuQHhH4ZxzLi3vKJxzzqXlHYVzzrm0vKNwzjmXlncUriBJ\napC0PGXplqbt9hZ4vEpJ6+NjLY2/3j3YYzwmqWdc/9U+9712uDHG4zTmZaWkP0vqkqH9WcVaKdXl\njn891hUkSdvNrFNLt01zjErgL2Y2U1J/4D4zO/MwjnfYMWU6rqTpwGoz+02a9iMIFXSvb+lY3JHD\nzyhcqyCpU5xrY6mkNyXtVzVW0vGS5qV84r4g3t5f0oK47zOSMr2BzwNOjfveEo+1UtJN8baOkp6X\ntCLePizePldSb0kTgQ4xjififdvjv09Juiwl5kpJQyWVSrpX0uI4T8BPEqRlAbGgm6Q+8Tkuk/Sa\npK/GXymPA4bFWIbF2KdJej22ba76rnOfle/66b740txC+CXx8rg8S6gi0Dne15Xwy9LGM+Lt8d9b\ngdvjeimh9lNXwht/x3j7L4A7mnm8SmBoXP8+sAg4B3gT6Ej45fsqoBcwBJiasm9F/Hcucf6LxphS\n2jTGeDkwPa63JVTy7ABcC4yJt7cDlgCnNBPn9pTn9wwwIG53BtrE9X7ArLg+ApiUsv8E4Kq43oVQ\n/6ljvv+/fSnspSBLeDgH7DSzsxo3JJUBEyR9B9hD+CT9eeD9lH0WA9Ni2+fMbLmkCwkT1bway5u0\nJXwSb869ksYQagCNJNQGetbMPokx/Am4AHgJuF/SPYTLVfMP4nm9CDwoqR0wAJhnZjvj5a4zJQ2N\n7SoIBfzW77N/B0nL4/P/F/BySvvpkroTSlSUHeDx+wODJN0Wt9sDJ8djOdcs7yhca/FD4DjgHDOr\nV6gO2z61gZnNix3JZUClpAeArcDLZnZlgscYbWYzGzckXdxcIzNbrTDvxUBgvKRXzGxckidhZp9K\nmgtcAgwjTLIDYcaxG8xsdoZD7DSzsySVE2ob/Qx4iDBZ0xwzuzwO/M89wP4ChpjZ20nidQ58jMK1\nHhXA5thJXATsNy+4wlzhH5jZVOAxwpSQC4HzJTWOOXSU1CPhY84HviepXFJHwmWj+ZK+COwwsz8Q\nCjI2N+9wfTyzac7ThGJsjWcnEN70RzXuI6lHfMxmWZjR8EbgVjWV2W8sFz0ipenHhEtwjWYDNyie\nXilUHnYuLe8oXGvxBNBb0pvA1cBbzbTpC6yQtIzwaf1BM9tCeON8UlI14bLT15I8oJktJYxdvE4Y\ns3jMzJYBZwCvx0tAdwLjm9l9ClDdOJi9j78SJpf6m4WpOyF0bDXAUkkrCWXj057xx1iqCZPy/Ba4\nOz731P3mAD0bB7MJZx5lMbZVcdu5tPzrsc4559LyMwrnnHNpeUfhnHMuLe8onHPOpeUdhXPOubS8\no3DOOZeWdxTOOefS8o7COedcWv8H3YfZ7H31ELwAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "foxbg-y5Mfv6",
        "colab_type": "text"
      },
      "source": [
        "#### OneVsAll AUC with weights"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6rpkWFyKMBr4",
        "colab_type": "code",
        "outputId": "f04c5197-8c86-4a33-b51b-312b38dd651e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "# setting a big weight to incorrectly classified object of class 1 (misclassified as 2)\n",
        "AUCs = eval_metric(classes, probas, weight=[1, 1, 1, 1, 1, 1, 1, 1, 10, 1], metric='AUC:type=OneVsAll')\n",
        "print('CalBoost OneVsAll AUC with weights:')\n",
        "print('AUC:class=0 = {0:.4f}, AUC:class=1 = {1:.4f}, AUC:class=2 = {2:.4f}'.format(AUCs[0], AUCs[1], AUCs[2]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CalBoost OneVsAll AUC with weights:\n",
            "AUC:class=0 = 0.9792, AUC:class=1 = 0.5333, AUC:class=2 = 0.2222\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ck3UOJHzM9Vv",
        "colab_type": "code",
        "outputId": "a1ee6816-2336-4a23-919b-9d9123427b7a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "# setting a big weight to correctly classified object of class 0\n",
        "AUCs = eval_metric(classes, probas, weight=[10, 1, 1, 1, 1, 1, 1, 1, 1, 1], metric='AUC:type=OneVsAll')\n",
        "print('CalBoost OneVsAll AUC with weights:')\n",
        "print('AUC:class=0 = {0:.4f}, AUC:class=1 = {1:.4f}, AUC:class=2 = {2:.4f}'.format(AUCs[0], AUCs[1], AUCs[2]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CalBoost OneVsAll AUC with weights:\n",
            "AUC:class=0 = 0.9881, AUC:class=1 = 0.8718, AUC:class=2 = 0.7222\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Cg01NPzHPz7b",
        "colab_type": "text"
      },
      "source": [
        "Weights of the objects would affect AUC values for all classes as all objects of the other classes are used in the calculation as objects of class 0.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "31Dm_yN_Mzzm",
        "colab_type": "text"
      },
      "source": [
        "OneVsAll AUC measures the ability of the classifier to distinguish objects of one class from another. \n",
        "\n",
        "An advantage of OneVsAll is the ability to monitor performance on different classes separately. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ghp4K-7NNk19",
        "colab_type": "text"
      },
      "source": [
        "## AUC$\\mu$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "mmQhGMrCToZr"
      },
      "source": [
        "AUC$\\mu$ could be simply used as an evaluation metric to prevent overfitting, while OneVsAll AUC could not as it contains a metric value for each class and AUCs for different classes may vary inconsistently during training. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d0W3_mPxOJiV",
        "colab_type": "text"
      },
      "source": [
        "Let's have a look at the AUC$\\mu$ formula:\n",
        "\n",
        "$$\n",
        "AUC\\mu = \\frac{2}{K(K - 1)}\\sum_{i<j} S(i, j) \n",
        "$$\n",
        "\n",
        "$K$ is a number of classes, $i < j ≤ K$ are the classes' numbers.\n",
        "\n",
        "$S(i, j)$ is a separability measure between classes $i$ and $j$ defined as:\n",
        "\n",
        "$$\n",
        "S(i, j) = \\frac{1}{n_i n_j}\\sum_{a \\in D_i, b \\in D_j} \\hat{I} \\circ O(y^{(a)}, y^{(b)}, \\hat{p}^{(a)}, \\hat{p}^{(b)}, v_{i, j}),\n",
        "$$\n",
        "\n",
        "where \n",
        "\n",
        "* $\\hat I$ is indicator function applied to results of $O$, which returns 1 if $O$ returns a positive value, 0 if $O$ returns a negative value, and 0.5 if $O$ returns 0.\n",
        "\n",
        "* $O$ is an orientation function indicating if the two instances are ordered correctly, incorrectly, or tied. $O$ returns a positive value if the predictions are ranked correctly, a negative\n",
        "value if they are ranked incorrectly, and 0 if their rank is\n",
        "tied. \n",
        "\n",
        "\n",
        "* $a$,  $b$ are objects from classes $i$, $j$ respectively, \n",
        "* $\\hat{p}^{(a)}$, $\\hat{p}^{(b)}$ are vectors of predicted probabilities of the object to belong to the classes,  \n",
        "* $y^{(a)}$, $y^{(b)}$ are true labels of objects $a$, $b$ (one-hot vectors),\n",
        "* $v_{i, j}$ is a two-class decision hyperplane normal vector.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WbnHenOEoQtu",
        "colab_type": "text"
      },
      "source": [
        "$O$ is caclulates as following:\n",
        "\n",
        "\n",
        "$O(y^{(a)}, y^{(b)}, \\hat{p}^{(a)}, \\hat{p}^{(b)}, v_{i, j}) = v_{i, j} (y^{(a)} - y^{(b)}) v_{i, j} (\\hat{p}^{(a)} - \\hat{p}^{(b)})$\n",
        "\n",
        "Vectors $v_{i, j}$ come from misclassification cost matrix $A$, which is defined manually following the learning task. \n",
        "\n",
        "$v_{i,j} = A_{i,.} - A_{j,.}$\n",
        "\n",
        "$A_{i,j}$ is the cost of classifying an instance as class $i$\n",
        "when its true class is $j$. Then $A$ defines a partition on the\n",
        "$(K − 1)$−simplex and induces decision boundaries between\n",
        "the $K$ classes. \n",
        "\n",
        "Default misclassification cost matrix values are 1 everywhere, except the diagonal where they are 0. It is called the argmax partition\n",
        "matrix as it assigns a class with maximal probability."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O74KRN3ffSbN",
        "colab_type": "text"
      },
      "source": [
        "Here is a partition for a 3-class classification problem with the argmax partition matrix A. For a user-defined partition matrix the boundaries (marked by arrows) are shifted.\n",
        "\n",
        "![argmax partition matrix visualisation](https://habrastorage.org/webt/h_/9y/jh/h_9yjhimj9yidj3y1nritttbhsc.jpeg)\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Bm_INN7WtBFZ",
        "colab_type": "text"
      },
      "source": [
        "Follow [the article](http://proceedings.mlr.press/v97/kleiman19a/kleiman19a.pdf) for more details."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4-ZFdL8HoLxc",
        "colab_type": "text"
      },
      "source": [
        "CatBoost allows us to set the misclassification cost matrix $A$ and objects' weights to calculate $AUC\\mu$. \n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sLMqrPczy_hz",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate $AUC\\mu$ for a very small example with 3 classes and 4 objects:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DEuwaCB9zHuW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "classes = np.array([2, 1, 0, 2])\n",
        "\n",
        "y = np.array([[0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 0, 1]])\n",
        "\n",
        "probas = np.array([[0.3, 0.5, 0.2], [0.4, 0.5, 0.1], [0.4, 0.15, 0.45], [0.05, 0.5, 0.45]])\n",
        "\n",
        "K = 3\n",
        "\n",
        "A = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "l4L1LiZP7UX1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_I(value):\n",
        "  if value > 0:\n",
        "    return 1\n",
        "  elif value == 0:\n",
        "    return 0.5\n",
        "  return 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_GTYVtl8_l59",
        "colab_type": "text"
      },
      "source": [
        "Let's compute $S(i, j)$ for each ordered classes' pair:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "53mt8CR3zyS6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# i = 0 (objects: y_2), j = 1 (objects: y_1) \n",
        "v_01 = A[0, :] - A[1, :]\n",
        "s_01 = get_I(v_01.dot(y[2] - y[1]) * v_01.dot(probas[2] - probas[1]))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8NVFcJP36hR2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# i = 0 (objects: y_2), j = 2 (objects: y_0, y_3) \n",
        "v_02 = A[0, :] - A[2, :]\n",
        "s_02 = 1 / (1 * 2) * (get_I(v_02.dot(y[2] - y[0]) * v_02.dot(probas[2] - probas[0])) + \\\n",
        "       get_I(v_02.dot(y[2] - y[3]) * v_02.dot(probas[2] - probas[3])))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mTFw-BjXz9fe",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# i = 1 (objects: y_1), j = 2 (objects: y_0, y_3) \n",
        "v_12 = A[1, :] - A[2, :]\n",
        "s_12 = 1 / (1 * 2) * (get_I(v_12.dot(y[1] - y[0]) * v_02.dot(probas[1] - probas[0])) + \\\n",
        "       get_I(v_12.dot(y[1] - y[3]) * v_02.dot(probas[1] - probas[3])))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SiKLa0i-8b6q",
        "colab_type": "code",
        "outputId": "9cb48966-9dec-441c-93f2-755fddf0ca1a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "AUC_mu = 2 / (K * (K - 1)) * (s_01 + s_02 + s_12)\n",
        "print('AUC_mu = {:.4f}'.format(AUC_mu))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC_mu = 0.8333\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SE5JUtmLAMcz",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate the same metric with Catboost $AUC\\mu$ and ensure everything is right:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YmHfHRL43d_V",
        "colab_type": "code",
        "outputId": "dee115d0-5bff-42fd-de96-90674ae83bf6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "print('Catboost AUC_mu = {:.4f}'.format(eval_metric(classes, probas.T, 'AUC:type=Mu')[0]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Catboost AUC_mu = 0.8333\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iC9NFTjNAjhm",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate OneVsAll AUC for the same data:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CPO1XKBh9tFW",
        "colab_type": "code",
        "outputId": "67a8821d-9dfb-453f-f2b3-00ff0fab8bbf",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "AUCs = eval_metric(classes, probas.T, metric='AUC:type=OneVsAll')\n",
        "print('AUC:class=0 = {0:.4f}, AUC:class=1 = {1:.4f}, AUC:class=2 = {2:.4f}'.format(AUCs[0], AUCs[1], AUCs[2]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC:class=0 = 0.8333, AUC:class=1 = 0.6667, AUC:class=2 = 0.6250\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bKSa8NcMAwD7",
        "colab_type": "text"
      },
      "source": [
        "As we can see OneVsAll AUC and $AUC\\mu$ are pretty high, but actually algorithm performance is bad, accuracy is 0.25. Thus it is reasonable to evaluate other important metrics during training.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EfKNeqC23mzf",
        "colab_type": "code",
        "outputId": "1db410d2-ff53-4897-be1f-cb2294a37987",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "print('Accuracy = {:.4f}'.format(eval_metric(classes, probas.T, metric='Accuracy')[0]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Accuracy = 0.2500\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-ytxYh2NFOl4",
        "colab_type": "text"
      },
      "source": [
        "#### $AUC\\mu$ with misclassification cost matrix and weights"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jfGlSrtzFRO3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "AUC = eval_metric(classes, probas.T, weight=[1, 10, 1, 1], metric='AUC:type=Mu;misclass_cost_matrix=0/0.5/2/1/0/1/0/0.5/0')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2LLiuZhbFZls",
        "colab_type": "code",
        "outputId": "217fb628-c184-40e8-8c9e-87ae7153d981",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "print('Catboost AUC_mu with weights = {:.4f}'.format(AUC[0]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Catboost AUC_mu with weights = 0.1667\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PKij1RTBTSlU",
        "colab_type": "text"
      },
      "source": [
        "$AUC\\mu$ is a good generalizing metric to estimate algorithm ability to separate classes in multiclassification problems. See more about different approaches to multiclass AUC calculation and their properties in section 4.3 of [the article](http://proceedings.mlr.press/v97/kleiman19a/kleiman19a.pdf).\n",
        "\n",
        "AUC$\\mu$ could be interpreted as an average of pairwise AUCs between the classes. AUC$\\mu$ is a single value unlike OneVsAll AUC and thus it could be used as an evaluation metric during training for overfitting detection and trees pruning."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jyzEdJbFtbYp",
        "colab_type": "text"
      },
      "source": [
        "# AUC for ranking"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Vo7gnlonxR3H",
        "colab_type": "text"
      },
      "source": [
        "There are two variants of AUC for Ranking in CatBoost."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YF-bFQ8vuCgE",
        "colab_type": "text"
      },
      "source": [
        "### The Classic AUC\n",
        "is used for models with Logloss and CrossEntropy loss functions. It has the same formula as AUC for binary classification:\n",
        "\n",
        "$$\n",
        "\\frac{\\sum I(a_i, a_j) w_i w_j}{\\sum{w_i w_j}} \n",
        "$$\n",
        "\n",
        "$a_i, a_j$ - predicted rank of objects i, j.\n",
        "\n",
        "The sum is calculated on all pairs of objects $i, j$ such that:\n",
        "$t_i = 0, t_j = 1$ where $t$ is relevance.\n",
        "\n",
        "$$\n",
        "I(a_i, a_j) =\n",
        "  \\begin{cases}\n",
        "    1    & \\quad \\text{if } a_i < a_j\\\\\n",
        "    0.5  & \\quad \\text{if } a_i = a_j\\\\\n",
        "    0    & \\quad \\text{if } a_i > a_j\\\\\n",
        "  \\end{cases}\n",
        "$$\n",
        "\n",
        "The formula above suits for simple tasks with target values equal to 1 and 0. What if we have more target values? \n",
        "\n",
        "If the target type is not binary, then every object $i$ with target value $t$ and weight $w$ is replaced with two objects for the metric calculation:\n",
        "\n",
        "* $\\sigma_1$ with weight $wt$ and target value 1\n",
        "* $\\sigma_2$ with weight $w(1 - t)$ and target value 0.\n",
        "\n",
        "Target values must be in the range [0; 1].\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wi6LmfLZ_d7x",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate Classic AUC for Ranking for a small example. Assume we have 2 documents, 2 requests, corresponding relevances in the range [1, 5] and predicted relevance in the range [0, 1]:\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "x-0sMVYH_17_",
        "colab_type": "code",
        "outputId": "18558f01-1b12-41c8-dfd2-621d3eda17de",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 166
        }
      },
      "source": [
        "rank_df = pd.DataFrame({'request_id': [1, 1, 2, 2], 'doc_id': [1, 2, 1, 2], 'relevance': [2, 5, 4, 1], 'pred':[0.3, 0.7, 0.2, 0.6], 'weight': [1, 1, 1, 1]})\n",
        "#map relevence to [0, 1]\n",
        "rank_df.loc[:, 'relevance'] /= 5\n",
        "rank_df.sort_values(by='pred', axis=0, inplace=True)\n",
        "rank_df"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>request_id</th>\n",
              "      <th>doc_id</th>\n",
              "      <th>relevance</th>\n",
              "      <th>pred</th>\n",
              "      <th>weight</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>0.8</td>\n",
              "      <td>0.2</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.4</td>\n",
              "      <td>0.3</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>2</td>\n",
              "      <td>2</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0.6</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.7</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   request_id  doc_id  relevance  pred  weight\n",
              "2           2       1        0.8   0.2       1\n",
              "0           1       1        0.4   0.3       1\n",
              "3           2       2        0.2   0.6       1\n",
              "1           1       2        1.0   0.7       1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 62
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GdfSC870D79e",
        "colab_type": "text"
      },
      "source": [
        "Let's create objects $\\sigma$ required for calculation and update weights:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yiIluHApETFU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "rank_df_sigma = pd.concat([\n",
        "    rank_df,rank_df\n",
        "],ignore_index=True)\n",
        "rank_df_sigma['new_relevance'] = 0\n",
        "rank_df_sigma.loc[:3, 'new_relevance'] = 1\n",
        "rank_df_sigma['new_weight'] = rank_df_sigma['weight']"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "01Jtfs2pFYqa",
        "colab_type": "code",
        "outputId": "d4247f83-2ae9-493c-f75b-d1e2105c037f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 284
        }
      },
      "source": [
        "rank_df_sigma.loc[rank_df_sigma['new_relevance'] == 1, 'new_weight'] = rank_df_sigma['relevance'] * rank_df_sigma['weight']\n",
        "rank_df_sigma.loc[rank_df_sigma['new_relevance'] == 0, 'new_weight'] = (1 - rank_df_sigma['relevance']) * rank_df_sigma['weight']\n",
        "rank_df_sigma.sort_values(by='pred', axis=0, ascending=False, inplace=True)\n",
        "rank_df_sigma"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>request_id</th>\n",
              "      <th>doc_id</th>\n",
              "      <th>relevance</th>\n",
              "      <th>pred</th>\n",
              "      <th>weight</th>\n",
              "      <th>new_relevance</th>\n",
              "      <th>new_weight</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.7</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>1.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>7</th>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.7</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>2</td>\n",
              "      <td>2</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0.6</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.2</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>6</th>\n",
              "      <td>2</td>\n",
              "      <td>2</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0.6</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.8</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.4</td>\n",
              "      <td>0.3</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.4</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.4</td>\n",
              "      <td>0.3</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.6</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>0.8</td>\n",
              "      <td>0.2</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.8</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>0.8</td>\n",
              "      <td>0.2</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0.2</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   request_id  doc_id  relevance  pred  weight  new_relevance  new_weight\n",
              "3           1       2        1.0   0.7       1              1         1.0\n",
              "7           1       2        1.0   0.7       1              0         0.0\n",
              "2           2       2        0.2   0.6       1              1         0.2\n",
              "6           2       2        0.2   0.6       1              0         0.8\n",
              "1           1       1        0.4   0.3       1              1         0.4\n",
              "5           1       1        0.4   0.3       1              0         0.6\n",
              "0           2       1        0.8   0.2       1              1         0.8\n",
              "4           2       1        0.8   0.2       1              0         0.2"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 66
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gRMCQhRS0Cj6",
        "colab_type": "text"
      },
      "source": [
        "Let's calculate AUC:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TYiTnRbOG1NY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# finding sum of weights for denominator\n",
        "weights1 = rank_df_sigma.loc[rank_df_sigma['new_relevance'] == 1, 'new_weight'].to_numpy()\n",
        "weights0 = rank_df_sigma.loc[rank_df_sigma['new_relevance'] == 0, 'new_weight'].to_numpy()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VYthlOpwhqgG",
        "colab_type": "text"
      },
      "source": [
        "Calculation details for object #3:\n",
        "\n",
        "![classical ranking AUC calculation](https://habrastorage.org/webt/gq/in/iy/gqiniyqqhdgpd3fqckbdlwgvk4w.jpeg)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mfuBVxJ6I7me",
        "colab_type": "code",
        "outputId": "afe49d91-db7a-446b-9190-5707fdf1298e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "denominator = np.sum(weights1.reshape(-1, 1)@weights0.reshape(1, -1))\n",
        "# for each object of class 1 find objects of class 0 below and add composition of weights and indicatior function to the numerator \n",
        "numerator = 1 * (0.8 + 0.6 + 0.2) + 0.2 * (0.8 * 0.5 + 0.6 + 0.2) + 0.4 * (0.6 * 0.5 + 0.2) + 0.8 * 0.2 * 0.5\n",
        "manually_calculated_auc = numerator / denominator\n",
        "print('Example of manually calculated Classic ROC AUC for ranking = {0:.4f}'.format(manually_calculated_auc))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Example of manually calculated Classic ROC AUC for ranking = 0.5521\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lo_MkDWKKa5S",
        "colab_type": "code",
        "outputId": "2e2d10d9-a8ce-45cf-ca3c-a5c5ceaa839c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "print('CatBoost Classic ROC AUC for ranking = {0:.4f}'.format(eval_metric(rank_df['relevance'], rank_df['pred'], 'AUC:type=Classic')[0]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CatBoost Classic ROC AUC for ranking = 0.5521\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zh_BXVF64IB_",
        "colab_type": "text"
      },
      "source": [
        "## Ranking AUC\n",
        "\n",
        "Ranking AUC is used for ranking loss functions.\n",
        "\n",
        "$$\n",
        "\\frac{\\sum I(a_i, a_j) w_i w_j}{\\sum{w_i w_j}} \n",
        "$$\n",
        "\n",
        "$a_i, a_j$ - predicted rank of objects i, j.\n",
        "\n",
        "The sum is calculated on all pairs of objects $i, j$ such that:\n",
        "$t_i < t_j$ where $t$ is relevance.\n",
        "\n",
        "$$\n",
        "I(a_i, a_j) =\n",
        "  \\begin{cases}\n",
        "    1    & \\quad \\text{if } a_i < a_j\\\\\n",
        "    0.5  & \\quad \\text{if } a_i = a_j\\\\\n",
        "    0    & \\quad \\text{if } a_i > a_j\\\\\n",
        "  \\end{cases}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bA8K_XglLhH1",
        "colab_type": "text"
      },
      "source": [
        "Let's compute Ranking AUC for the small example above:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AtzoAj6MLqet",
        "colab_type": "code",
        "outputId": "3d7e5dda-9b62-4372-b9a6-a6e7150791c3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 166
        }
      },
      "source": [
        "rank_df.sort_values(by='relevance', axis=0, inplace=True, ascending=False)\n",
        "rank_df"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>request_id</th>\n",
              "      <th>doc_id</th>\n",
              "      <th>relevance</th>\n",
              "      <th>pred</th>\n",
              "      <th>weight</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.7</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>0.8</td>\n",
              "      <td>0.2</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0.4</td>\n",
              "      <td>0.3</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>2</td>\n",
              "      <td>2</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0.6</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   request_id  doc_id  relevance  pred  weight\n",
              "1           1       2        1.0   0.7       1\n",
              "2           2       1        0.8   0.2       1\n",
              "0           1       1        0.4   0.3       1\n",
              "3           2       2        0.2   0.6       1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 70
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eFrN1wpQNS-3",
        "colab_type": "text"
      },
      "source": [
        "Calculation details:\n",
        "\n",
        "![ranking AUC calculation details](https://habrastorage.org/webt/rk/8w/ka/rk8wkacwlc9sw3tqq2bgitqti-m.jpeg)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EPoAl92NLsCl",
        "colab_type": "code",
        "outputId": "126ed541-ce40-4945-b680-8421ad5bc46f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "n = rank_df['relevance'].unique().shape[0]\n",
        "denominator = (n * (n-1)) / 2 #number of ordered pairs\n",
        "# for object #1 three object below are less relevant by real relevance and predictions, the other are incorrectly ranked \n",
        "numerator = 3\n",
        "manually_calculated_auc = numerator / denominator\n",
        "print('Example of manually calculated Ranking ROC AUC = {0:.4f}'.format(manually_calculated_auc))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Example of manually calculated Ranking ROC AUC = 0.5000\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3J7C-V3eNCHa",
        "colab_type": "code",
        "outputId": "bc6c1c35-7e6e-46f2-8ee1-95b4f65b2ed1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "print('CatBoost Ranking ROC AUC = {0:.4f}'.format(eval_metric(rank_df['relevance'], rank_df['pred'], 'AUC:type=Ranking', group_id=rank_df['request_id'])[0]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CatBoost Ranking ROC AUC = 0.5000\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IQ2zjs34NuMh",
        "colab_type": "text"
      },
      "source": [
        "Ranking AUC is directly measuring the quantity of correctly ranked pairs. The problem is the metric is calculated regardless of groups. In our example, we have groups (requests) and we may want to measure quality inside the groups, but currently, AUC is calculated over the dataset and AUC penalizes us if, for example, top-one document for one request is ranked lower than top-one for another document while true ranks are opposite (but still top-one for each document).\n",
        "\n",
        "One more problem of AUC for Ranking is that it does not distinguish the top object from the others. If we have a lot of irrelevant documents, which are ranked irrelevant by the model, but bad ranking in top-10, AUC could still be high because of that \"tail\" of irrelevant objects, ranked lower than relevant. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "K2zjAF0p8Adf",
        "colab_type": "text"
      },
      "source": [
        "#Overview\n",
        "\n",
        "AUC is a widely used metric to measure the ability of a model to distinguish classes and correctly order objects from different classes / with different relevance. AUC is not differentiable and thus cannot be used as a loss function, but it is pretty informative and useful as a metric. \n",
        "\n",
        "We have examined the following AUC types:\n",
        "* AUC for binary classification. It is a classical metric, which measures the model quality. ROC curve allows selecting the probability threshold to meet required False Positive or False Negative Rates. \n",
        "\n",
        "* AUC for multiclass classification: OneVsAll and $AUC\\mu$. OneVsAll AUC helps to control algorithm performance for each class, but can not be used as a metric to prevent overfitting. On the contrary, $AUC\\mu$ is good as a generalizing metric, but will not detect a problem with one class.\n",
        "\n",
        "* AUC for ranking: Classic AUC and Ranking AUC. AUC suits for ranking tasks because it is designed to measure how the algorithm distinguishes between classes and it is simply transferring to distinguishing between relevant and irrelevant objects. But AUC does not take into account that in ranking problems the first $n$ positions are very important and treats each correctly ordered pair of documents equally.   \n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BP1nOBpvFzPV",
        "colab_type": "text"
      },
      "source": [
        "# How to use AUC in Catboost on real datasets? \n",
        "\n",
        "AUC implemented in CatBoost allows using weights to consider object and classes' importance in metric calculation. \n",
        "You can use AUC in Catboost during training as a validation metric to prevent overfitting and select the best model and as a metric to compare different models' results. \n",
        "\n",
        "Let's consider an example of using AUC for a multiclassification task."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Srr6fg6agch_"
      },
      "source": [
        "### AUC for multiclass classification"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "exFbBmAHgciQ"
      },
      "source": [
        "#### Loading dataset"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "xgtP8tQugciS"
      },
      "source": [
        "We will use the [Wine recognition dataset](https://scikit-learn.org/stable/datasets/index.html#wine-dataset ) for multiclass classification problem"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GvRX3NiZgSiM",
        "colab_type": "code",
        "outputId": "4dbda0c6-e453-402c-d8a2-4253c8cfec00",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 202
        }
      },
      "source": [
        "!wget https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2020-03-29 14:50:55--  https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data\n",
            "Resolving archive.ics.uci.edu (archive.ics.uci.edu)... 128.195.10.252\n",
            "Connecting to archive.ics.uci.edu (archive.ics.uci.edu)|128.195.10.252|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 10782 (11K) [application/x-httpd-php]\n",
            "Saving to: ‘wine.data’\n",
            "\n",
            "\rwine.data             0%[                    ]       0  --.-KB/s               \rwine.data           100%[===================>]  10.53K  --.-KB/s    in 0s      \n",
            "\n",
            "2020-03-29 14:50:55 (118 MB/s) - ‘wine.data’ saved [10782/10782]\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m95K_uLkhmtc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "columns = ['Class', 'Alcohol', 'Malic_acid', 'Ash', 'Alcalinity_of_ash', 'Magnesium', 'Total_phenols', 'Flavanoids', 'Nonflavanoid_phenols', 'Proanthocyanins', 'Color_intensity', 'Hue', 'OD280OD315_of_diluted_wines', 'Proline']\n",
        "train_df = pd.read_csv('wine.data', names=columns)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "X7__C4NvhsKV",
        "colab_type": "code",
        "outputId": "6e6b45a8-f5c9-48b9-ba2c-b4f519bb23b1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 215
        }
      },
      "source": [
        "train_df.head(5)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>Class</th>\n",
              "      <th>Alcohol</th>\n",
              "      <th>Malic_acid</th>\n",
              "      <th>Ash</th>\n",
              "      <th>Alcalinity_of_ash</th>\n",
              "      <th>Magnesium</th>\n",
              "      <th>Total_phenols</th>\n",
              "      <th>Flavanoids</th>\n",
              "      <th>Nonflavanoid_phenols</th>\n",
              "      <th>Proanthocyanins</th>\n",
              "      <th>Color_intensity</th>\n",
              "      <th>Hue</th>\n",
              "      <th>OD280OD315_of_diluted_wines</th>\n",
              "      <th>Proline</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>14.23</td>\n",
              "      <td>1.71</td>\n",
              "      <td>2.43</td>\n",
              "      <td>15.6</td>\n",
              "      <td>127</td>\n",
              "      <td>2.80</td>\n",
              "      <td>3.06</td>\n",
              "      <td>0.28</td>\n",
              "      <td>2.29</td>\n",
              "      <td>5.64</td>\n",
              "      <td>1.04</td>\n",
              "      <td>3.92</td>\n",
              "      <td>1065</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>13.20</td>\n",
              "      <td>1.78</td>\n",
              "      <td>2.14</td>\n",
              "      <td>11.2</td>\n",
              "      <td>100</td>\n",
              "      <td>2.65</td>\n",
              "      <td>2.76</td>\n",
              "      <td>0.26</td>\n",
              "      <td>1.28</td>\n",
              "      <td>4.38</td>\n",
              "      <td>1.05</td>\n",
              "      <td>3.40</td>\n",
              "      <td>1050</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>1</td>\n",
              "      <td>13.16</td>\n",
              "      <td>2.36</td>\n",
              "      <td>2.67</td>\n",
              "      <td>18.6</td>\n",
              "      <td>101</td>\n",
              "      <td>2.80</td>\n",
              "      <td>3.24</td>\n",
              "      <td>0.30</td>\n",
              "      <td>2.81</td>\n",
              "      <td>5.68</td>\n",
              "      <td>1.03</td>\n",
              "      <td>3.17</td>\n",
              "      <td>1185</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>1</td>\n",
              "      <td>14.37</td>\n",
              "      <td>1.95</td>\n",
              "      <td>2.50</td>\n",
              "      <td>16.8</td>\n",
              "      <td>113</td>\n",
              "      <td>3.85</td>\n",
              "      <td>3.49</td>\n",
              "      <td>0.24</td>\n",
              "      <td>2.18</td>\n",
              "      <td>7.80</td>\n",
              "      <td>0.86</td>\n",
              "      <td>3.45</td>\n",
              "      <td>1480</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>1</td>\n",
              "      <td>13.24</td>\n",
              "      <td>2.59</td>\n",
              "      <td>2.87</td>\n",
              "      <td>21.0</td>\n",
              "      <td>118</td>\n",
              "      <td>2.80</td>\n",
              "      <td>2.69</td>\n",
              "      <td>0.39</td>\n",
              "      <td>1.82</td>\n",
              "      <td>4.32</td>\n",
              "      <td>1.04</td>\n",
              "      <td>2.93</td>\n",
              "      <td>735</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   Class  Alcohol  Malic_acid  ...   Hue  OD280OD315_of_diluted_wines  Proline\n",
              "0      1    14.23        1.71  ...  1.04                         3.92     1065\n",
              "1      1    13.20        1.78  ...  1.05                         3.40     1050\n",
              "2      1    13.16        2.36  ...  1.03                         3.17     1185\n",
              "3      1    14.37        1.95  ...  0.86                         3.45     1480\n",
              "4      1    13.24        2.59  ...  1.04                         2.93      735\n",
              "\n",
              "[5 rows x 14 columns]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 79
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "K_cK1n1egcik"
      },
      "source": [
        "#### Creating pool"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "outputId": "4c99f135-dee0-4dd3-bb38-2fcd5a894d94",
        "id": "aphHeJQigcil",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "y = train_df['Class']\n",
        "X = train_df.drop(columns='Class')\n",
        "y.unique()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([1, 2, 3])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 80
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "mHri4tjqgciv",
        "colab": {}
      },
      "source": [
        "from sklearn.model_selection import train_test_split\n",
        "X_train, X_validation, y_train, y_validation = train_test_split(X, y, train_size=0.5, random_state=42)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "_Nz4OMFigciy",
        "colab": {}
      },
      "source": [
        "train_pool = Pool(X_train, y_train)\n",
        "validation_pool = Pool(X_validation, y_validation)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "P_DQ-nsjgci0"
      },
      "source": [
        "#### Training model"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "outputId": "6accb4eb-5c33-4fd0-80ce-c776488d0cf5",
        "id": "wfIuw-4egci1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 454
        }
      },
      "source": [
        "from catboost import CatBoostClassifier\n",
        "model = CatBoostClassifier(\n",
        "    iterations=20,\n",
        "    eval_metric='AUC',\n",
        "    custom_metric=['AUC:type=OneVsAll;hints=skip_train~false', 'Accuracy'],\n",
        "    # metric_period=10,\n",
        "    loss_function='MultiClass',\n",
        "    train_dir='model_dir',\n",
        "    random_seed=42)\n",
        "\n",
        "model.fit(\n",
        "    train_pool,\n",
        "    eval_set=validation_pool,\n",
        "    verbose=True, \n",
        ");"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Learning rate set to 0.458482\n",
            "0:\ttest: 0.9222371\tbest: 0.9222371 (0)\ttotal: 3.39ms\tremaining: 64.5ms\n",
            "1:\ttest: 0.9777926\tbest: 0.9777926 (1)\ttotal: 6.04ms\tremaining: 54.4ms\n",
            "2:\ttest: 0.9846999\tbest: 0.9846999 (2)\ttotal: 8.45ms\tremaining: 47.9ms\n",
            "3:\ttest: 0.9808378\tbest: 0.9846999 (2)\ttotal: 10.7ms\tremaining: 42.7ms\n",
            "4:\ttest: 0.9787582\tbest: 0.9846999 (2)\ttotal: 13.2ms\tremaining: 39.5ms\n",
            "5:\ttest: 0.9763815\tbest: 0.9846999 (2)\ttotal: 15.5ms\tremaining: 36.1ms\n",
            "6:\ttest: 0.9786096\tbest: 0.9846999 (2)\ttotal: 17.9ms\tremaining: 33.3ms\n",
            "7:\ttest: 0.9786096\tbest: 0.9846999 (2)\ttotal: 20.4ms\tremaining: 30.6ms\n",
            "8:\ttest: 0.9839572\tbest: 0.9846999 (2)\ttotal: 22.6ms\tremaining: 27.6ms\n",
            "9:\ttest: 0.9839572\tbest: 0.9846999 (2)\ttotal: 25ms\tremaining: 25ms\n",
            "10:\ttest: 0.9839572\tbest: 0.9846999 (2)\ttotal: 27.5ms\tremaining: 22.5ms\n",
            "11:\ttest: 0.9848485\tbest: 0.9848485 (11)\ttotal: 30ms\tremaining: 20ms\n",
            "12:\ttest: 0.9854427\tbest: 0.9854427 (12)\ttotal: 32.4ms\tremaining: 17.4ms\n",
            "13:\ttest: 0.9854427\tbest: 0.9854427 (12)\ttotal: 35.3ms\tremaining: 15.1ms\n",
            "14:\ttest: 0.9857398\tbest: 0.9857398 (14)\ttotal: 38.4ms\tremaining: 12.8ms\n",
            "15:\ttest: 0.9869281\tbest: 0.9869281 (15)\ttotal: 41.1ms\tremaining: 10.3ms\n",
            "16:\ttest: 0.9875223\tbest: 0.9875223 (16)\ttotal: 43.6ms\tremaining: 7.69ms\n",
            "17:\ttest: 0.9884135\tbest: 0.9884135 (17)\ttotal: 45.9ms\tremaining: 5.1ms\n",
            "18:\ttest: 0.9878194\tbest: 0.9884135 (17)\ttotal: 48.3ms\tremaining: 2.54ms\n",
            "19:\ttest: 0.9881165\tbest: 0.9884135 (17)\ttotal: 50.6ms\tremaining: 0us\n",
            "\n",
            "bestTest = 0.9884135472\n",
            "bestIteration = 17\n",
            "\n",
            "Shrink model to first 18 iterations.\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CuoU4zXOAwjj",
        "colab_type": "text"
      },
      "source": [
        "Model is shrinked to the first best $AUC\\mu$ value (17 iteration)  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3c-zedeC97gb",
        "colab_type": "text"
      },
      "source": [
        "#### Calculating metrics"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "juhEuO8lljMJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "AUCs = model.eval_metrics(validation_pool, metrics=['AUC:type=Mu', 'AUC:type=OneVsAll'])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "k6U6kaQ9l4dW",
        "colab_type": "code",
        "outputId": "97f3910a-2524-459d-910b-5ca7babad5fe",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 101
        }
      },
      "source": [
        "print('AUC:type=OneVsAll:')\n",
        "print('AUC:class=0 = {0:.4f}, AUC:class=1 = {1:.4f}, AUC:class=2 = {2:.4f}'.format(AUCs['AUC:class=0'][-1], AUCs['AUC:class=1'][-1], AUCs['AUC:class=2'][-1]))\n",
        "\n",
        "print('\\nAUC:type=Mu:')\n",
        "print('AUC:type=Mu = {0:.5f}'.format(AUCs['AUC:type=Mu'][-1]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC:type=OneVsAll:\n",
            "AUC:class=0 = 0.9827, AUC:class=1 = 0.9690, AUC:class=2 = 1.0000\n",
            "\n",
            "AUC:type=Mu:\n",
            "AUC:type=Mu = 0.98841\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8Rl9rEsi9pAJ",
        "colab_type": "text"
      },
      "source": [
        "Using weigths and misclassification cost matrix:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "45iYcMbi-NVc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "weights = np.random.rand(X_validation.shape[0])\n",
        "weights[10] = 100\n",
        "validation_pool = Pool(X_validation, y_validation, weight=weights)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5fC8mYED-Yr5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "AUC = model.eval_metrics(validation_pool, metrics=['AUC:type=Mu', 'AUC:type=Mu;use_weights=True', 'AUC:type=Mu;misclass_cost_matrix=0/0.5/2/1/0/1/0/0.5/0;use_weights=True'])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T7JGEog9_GCj",
        "colab_type": "code",
        "outputId": "bea6a119-1983-44b7-eb21-c52e5381374a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        }
      },
      "source": [
        "print('AUC:type=Mu = {0:.5f}'.format(AUC['AUC:type=Mu'][-1]))\n",
        "print('AUC:type=Mu;use_weights=True = {0:.5f}'.format(AUC['AUC:use_weights=true;type=Mu'][-1]))\n",
        "print('AUC:use_weights=true;type=Mu;misclass_cost_matrix = {0:.5f}'.format(AUC['AUC:use_weights=true;type=Mu;misclass_cost_matrix=0/0.5/2/1/0/1/0/0.5/0'][-1]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "AUC:type=Mu = 0.98841\n",
            "AUC:type=Mu;use_weights=True = 0.94668\n",
            "AUC:use_weights=true;type=Mu;misclass_cost_matrix = 0.96956\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}